※記法については『算数の問題文の記法のまとめ【随時更新】 - 算数の問題文の記法を考える』を読んでください。
【2000年度ジュニア算数オリンピックトライアル問題6問目】
下の10個の◇の中に1から10までの数を1つずつ入れて3つの❖の中の数の和が等しくなるようにしなさい。
【記法化】
n_table := [
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
];
実行;
[n_table[0][0], n_table[0][1], n_table[1][0], n_table[1][1], n_table[1][2], n_table[2][1], n_table[2][2], n_table[2][3], n_table[3][2], n_table[3][3]].every := 被りなしで挿入 : 被りなしで全て移動 := [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].every;
実行;
n_table[0][0] + n_table[0][1] + n_table[1][0] + n_table[1][1] == n_table[1][1] + n_table[1][2] + n_table[2][1] + n_table[2][2] == n_table[2][2] + n_table[2][3] + n_table[3][2] + n_table[3][3];
print(n_table);
【工夫】
2度数える部分をa、bとして、1+2+3+4+5+6+7+8+9+10+a+bが3の倍数でなければならない。よってa+bの候補は5、8、11、14、17。そのそれぞれで正解を見つけることができるらしい。5の場合、❖内は20なのでそうなるようにする。
正直記述が難しい所以外は普通の制約の問題であるし、最適化方法をここで考えるのはよそうと思う。
ちなみにCP-SAT ソルバー | OR-Tools | Google for Developersで普通に解くとこうなる。
from ortools.sat.python import cp_model model = cp_model.CpModel() num_vals = 11 A = model.new_int_var(1, num_vals - 1, "A") B = model.new_int_var(1, num_vals - 1, "B") C = model.new_int_var(1, num_vals - 1, "C") D = model.new_int_var(1, num_vals - 1, "D") E = model.new_int_var(1, num_vals - 1, "E") F = model.new_int_var(1, num_vals - 1, "F") G = model.new_int_var(1, num_vals - 1, "G") H = model.new_int_var(1, num_vals - 1, "H") I = model.new_int_var(1, num_vals - 1, "I") J = model.new_int_var(1, num_vals - 1, "J") model.add_all_different([A, B, C, D, E, F, G, H, I, J]) model.add(A + B + C + D == D + E + F + G) model.add(D + E + F + G == G + H + I + J) solver = cp_model.CpSolver() status = solver.solve(model) if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE: print(f"A = {solver.value(A)}") print(f"B = {solver.value(B)}") print(f"C = {solver.value(C)}") print(f"D = {solver.value(D)}") print(f"E = {solver.value(E)}") print(f"F = {solver.value(F)}") print(f"G = {solver.value(G)}") print(f"H = {solver.value(H)}") print(f"I = {solver.value(I)}") print(f"J = {solver.value(J)}") else: print("No solution found.")
コードを流用したけどnum_valsってどういう意味なんだろう。数字の値ぐらいの認識で良いんだろうか。
結果
A = 1 B = 5 C = 8 D = 10 E = 3 F = 4 G = 7 H = 6 I = 2 J = 9
