問題: 5 行 4 列の正方形のグリッドがあります。これらの数値を使用してグリッドを埋める必要があります。1,2,3,4,5,6,7,8,9,10,12,18,20,21,24,27,30,35,36,40. 水平方向と垂直方向のすべての隣人が残りなく他のものを分割するように、グリッドを埋める必要があります。たとえば、12and3は隣人になることができます12 % 3 == 0が、5and 12 はそうではありません。グリッド 2x2 は となります10。
セットのリストを使用して問題を解決しようとしました。各セットは、各グリッドの可能な値を表します。すべてのセットに要素が 1 つしかない場合、問題は解決されます。この問題を解決するために使用する関数を次に示します (念のためすべてを追加しましたが、私の問題は解決関数にあると思います)。
class CannotSolveError(Exception):
pass
def suitable_neighbor(a,b):
"return True if a and b can be neighbors."
return (a > b) and (a % b == 0) or (b % a == 0)
def equalize_tables(table1, table2):
"Make two tables equal, by changing first one in-place"
for i in range(len(table1)):
table1[i] = table2[i]
def remove_possibility(table, row, column, value):
"""Remove possibilities that can't be neighbors with value in rowxcolumn grid."""
index = ((row - 1) * num_cols) + column - 1
if len(table[index]) == 1:
return # This is a solved grid, do nothing.
remaining_possibilities = set(
filter(lambda x: suitable_neighbor(x, value), table[index])
)
if not remaining_possibilities:
raise ValueError("Invalid move")
if len(remaining_possibilities) == 1:
"Only one possibility remains, try to put it!"
copy_table = table[:]
try:
"Try it on copy"
put(copy_table, row, column, remaining_possibilities.pop())
except ValueError:
"Cannot put, re-raise and do nothing.."
raise
else:
"Putting is successfull, update original table"
equalize_tables(table, copy_table)
else:
table[index] = remaining_possibilities
def put(table, row, column, value):
"""Put a value on a grid, modifies given table. use with care!"""
index = ((row - 1) * num_cols) + column - 1
"Is this move possible?"
if value not in table[index]:
raise ValueError("Cannot put %d on %dx%d" % (value, row, column))
"Remove possibilities from left neighbor"
if column > 1:
remove_possibility(table, row, column - 1, value)
"Remove possibilities from right neighbor"
if column < num_cols:
remove_possibility(table, row, column + 1, value)
"Remove possibilities from upper neighbor"
if row > 1:
remove_possibility(table, row - 1, column, value)
"Remove possibilities from lower neighbor"
if row < num_rows:
remove_possibility(table, row + 1, column, value)
"Remove this value from every other set."
for i in range(num_rows * num_cols):
if i == index:
continue
table[i].discard(value)
"Put one-item set in place. Have to do this last."
table[index] = set([value])
def solve(table):
"Try to solve the table by trying possible values on grids."
to_try = [(i,len(table[i])) for i in range(num_rows * num_cols) if len(table[i]) > 1]
"Grid with least remaining possibilities will be tried first."
to_try.sort(key = lambda x: x[1])
for index, _ in to_try:
for value in table[index]:
row = index / num_cols + 1
column = index % num_cols + 1
copy_table = table[:]
put(copy_table, row, column, value)
try:
solve(copy_table)
equalize_tables(table, copy_table)
return
except CannotSolveError:
continue
except ValueError:
continue
raise CannotSolveError
このアルゴリズムは問題を解決するはずだと思います。しかし、最大再帰深度を超えています。これを回避する方法、または Python でこの問題をより適切に解決するにはどうすればよいですか?
これは宿題の質問ではありません。私は自分でこれに取り組んでいます。