クローンナンプレ(数独)の解法で数字が置き換わってしまいます

実現したいこと

こちらに何度か質問させて頂いていて、数独
(ナンプレ)の特殊問題の解法も可能になって
きましたけれど、ここで、クローンナンプレ
という特殊問題の解法でまたまた詰まって
しまいました。

前提

下記URLの問題は、ルールは通常の数独の
ルール(縦・横・3x3)に加えて、セルの色
が濃くなっています2か所が同じ形をして
いまして、同じ場所のセルに同じ数字が
入るというものです。

発生している問題・エラーメッセージ

クローンナンプレですので、プログラム上に
grid[ 0 ][ 4 ]の値をgrid[ 5 ][ 1 ]へとコピー
しなさいという命令を書いたつもりですが、
後半へと進んでいくとgrid[ 5 ][ 1 ]が書き換え
られてしまいます。
grid[ 0 ][ 4 ] =  7
grid[ 5 ][ 1 ] =  7　←(0,4)直後に値が入るものの…
grid[ 0 ][ 4 ] =  9
grid[ 5 ][ 1 ] =  9　←次に(0,4)が出た時にちゃんと書き換わるものの

grid[ 5 ][ 0 ] =  8
grid[ 5 ][ 1 ] =  1
grid[ 5 ][ 2 ] =  5
として、grid[ 5 ]行目のチェックで、数値が
置き換わってしまいます。

該当のソースコード

python
1# https://note.com/motchalini/n/n00af5def35a4 より
2
3backtracks = 0
4
5input_grid = [[0, 2, 3, 4, 0, 0, 0, 0, 0],
6              [4, 0, 0, 0, 5, 0, 0, 0, 0],
7              [0, 0, 0, 0, 0, 0, 0, 8, 0],
8              [6, 0, 0, 3, 0, 0, 0, 0, 0],
9              [0, 7, 4, 0, 0, 0, 9, 6, 0],
10              [0, 0, 0, 0, 0, 9, 0, 0, 7],
11              [0, 5, 0, 0, 0, 0, 0, 0, 0],
12              [0, 0, 0, 0, 8, 0, 0, 0, 5],
13              [0, 0, 0, 0, 0, 3, 1, 2, 0]]
14
15
16def find_next_cell(grid):
17    for y in range(9):
18        for x in range(9):
19            if grid[y][x] == 0:
20                # 0 の座標を返す
21                return y, x
22    # すべてのマスに数字が入っている状態
23    return -1, -1
24
25
26def is_valid(grid, y, x, value):
27    # 行のチェック
28    is_row = value not in grid[y]
29    # 列のチェック
30    is_column = value not in [i[x] for i in grid]
31    # ブロックを取り出す
32    blk_x, blk_y = (x//3) * 3, (y//3) * 3
33    blk_grid = [i[blk_x:blk_x + 3] for i in grid[blk_y:blk_y + 3]]
34    # ブロックのチェック
35    is_block = value not in sum(blk_grid, [])
36    # 有効チェック
37    return all([is_row, is_column, is_block])
38
39
40def solve_sudoku(grid, y=0, x=0):
41    global backtracks
42    y, x = find_next_cell(grid)
43    # 終了判定
44    if y == -1 or x == -1:
45        return True
46    # 入力
47    for value in range(1, 10):
48        if is_valid(grid, y, x, value):
49            grid[y][x] = value
50            print('grid[',y,'][',x,'] = ',value)
51            if y==0 and x==4:
52                y2 = 5 ; x2 = 1
53                if solve_sudoku2(grid, y2, x2, value):
54                    grid[y2][x2] = value
55                    return True
56                grid[y2][x2] = 0
57            elif y==1 and x==3:
58                y2 = 6 ; x2 = 0
59                if solve_sudoku2(grid, y2, x2, value):
60                    grid[y2][x2] = value
61                    return True
62                grid[y2][x2] = 0
63            elif y==1 and x==5:
64                y2 = 6 ; x2 = 2
65                if solve_sudoku2(grid, y2, x2, value):
66                    grid[y2][x2] = value
67                    return True
68                grid[y2][x2] = 0
69            elif y==1 and x==7:
70                y2 = 6 ; x2 = 4
71                if solve_sudoku2(grid, y2, x2, value):
72                    grid[y2][x2] = value
73                    return True
74                grid[y2][x2] = 0
75            elif y==1 and x==8:
76                y2 = 6 ; x2 = 5
77                if solve_sudoku2(grid, y2, x2, value):
78                    grid[y2][x2] = value
79                    return True
80                grid[y2][x2] = 0
81            elif y==2 and x==4:
82                y2 = 7 ; x2 = 1
83                if solve_sudoku2(grid, y2, x2, value):
84                    grid[y2][x2] = value
85                    return True
86                grid[y2][x2] = 0
87            elif y==2 and x==5:
88                y2 = 7 ; x2 = 2
89                if solve_sudoku2(grid, y2, x2, value):
90                    grid[y2][x2] = value
91                    return True
92                grid[y2][x2] = 0
93            elif y==2 and x==6:
94                y2 = 7 ; x2 = 3
95                if solve_sudoku2(grid, y2, x2, value):
96                    grid[y2][x2] = value
97                    return True
98                grid[y2][x2] = 0
99            elif y==2 and x==8:
100                y2 = 7 ; x2 = 5
101                if solve_sudoku2(grid, y2, x2, value):
102                    grid[y2][x2] = value
103                    return True
104                grid[y2][x2] = 0
105            elif y==3 and x==4:
106                y2 = 8 ; x2 = 1
107                if solve_sudoku2(grid, y2, x2, value):
108                    grid[y2][x2] = value
109                    return True
110                grid[y2][x2] = 0
111            elif y==3 and x==5:
112                y2 = 8 ; x2 = 2
113                if solve_sudoku2(grid, y2, x2, value):
114                    grid[y2][x2] = value
115                    return True
116                grid[y2][x2] = 0
117            elif y==3 and x==6:
118                y2 = 8 ; x2 = 3
119                if solve_sudoku2(grid, y2, x2, value):
120                    grid[y2][x2] = value
121                    return True
122                grid[y2][x2] = 0
123            else:
124                # 次へ
125                if solve_sudoku(grid, y, x):
126                    return True
127                backtracks += 1
128                grid[y][x] = 0
129    return False
130
131
132def solve_sudoku2(grid, y2, x2, value):
133    global backtracks
134    grid[y2][x2] = value
135    print('grid[',y2,'][',x2,'] = ',value)
136    if is_valid2(grid, y2, x2, value):
137        return True
138    return False
139
140
141def is_valid2(grid2, y2, x2, value):
142    # 行のチェック
143    is_row2 = value not in grid2[y2]
144    # 列のチェック
145    is_column2 = value not in [i2[x2] for i2 in grid2]
146    # ブロックを取り出す
147    blk_x2, blk_y2 = (x2//3) * 3, (y2//3) * 3
148    blk_grid2 = [i2[blk_x2:blk_x2 + 3] for i2 in grid2[blk_y2:blk_y2 + 3]]
149    # ブロックのチェック
150    is_block2 = value not in sum(blk_grid2, [])
151    # 有効チェック
152    return all([is_row2, is_column2, is_block2])
153
154
155print(solve_sudoku(input_grid))
156print(backtracks)
157[print(i) for i in input_grid]
158

試したこと

サブルーチンをクローンの場所専用に独立
させましたつもりですがダメでした。

補足情報（FW/ツールのバージョンなど）

問題の写真は以下です
https://imgur.com/9F1SZkx.png

winterboum

2025/02/07 01:00

「として、grid[ 5 ]行目のチェックで、数値が置き換わってしまいます。」は codeのどこでですか？

ghon

2025/02/07 01:26

まず51行目の(y,x)=(0,4)にて、(5,1)のセルの中身が置き換わるのかと思うのですが if y==0 and x==4: y2 = 5 ; x2 = 1 if solve_sudoku2(grid, y2, x2, value): grid[y2][x2] = value return True 19行目の『ゼロ』のセルの位置を返します判定で、 if grid[5][1] == 0: がTrueと判定されてしまいます。 if grid[y][x] == 0: # 0 の座標を返す return y, x この(5,1)がゼロになっています理由がわかりませんでして…

行動規範の内容に同意します

回答1件

ベストアンサー

後半へと進んでいくとgrid[ 5 ][ 1 ]が書き換えられてしまいます。

ソースコードをざっと見る限り、値のチェックと値の設定は以下の順番で実行する必要があります。

is_validを使って、対象のセルに値を設定できるかどうかをチェック
OKなら対象のセルに値を設定する

しかし、solve_sudoku2を見ると、以下のようになっています。

対象のセルに値を設定する
is_valid2を呼び出して、対象のセルに値を設定できるかどうかをチェック

つまり、値を設定済みのセルに対して、チェック処理を行っており、これが原因で想定通り動かないのだと思います。

サブルーチンをクローンの場所専用に独立させましたつもりですがダメでした。

わざわざこのようなことをする必要はなく、solve_sudokuを以下の通り修正すればよいかと思います。

python
1clone_cells = {
2    (0,4) : (5,1),
3    (1,3) : (6,0),
4    (1,5) : (6,2),
5    (1,7) : (6,4),
6    (1,8) : (6,5),
7    (2,4) : (7,1),
8    (2,5) : (7,2),
9    (2,6) : (7,3),
10    (2,8) : (7,5),
11    (3,4) : (8,1),
12    (3,5) : (8,2),
13    (3,6) : (8,3),
14    
15    (5,1) : (0,4),
16    (6,0) : (1,3),
17    (6,2) : (1,5),
18    (6,4) : (1,7),
19    (6,5) : (1,8),
20    (7,1) : (2,4),
21    (7,2) : (2,5),
22    (7,3) : (2,6),
23    (7,5) : (2,8),
24    (8,1) : (3,4),
25    (8,2) : (3,5),
26    (8,3) : (3,6),
27}
28
29
30def solve_sudoku(grid, y=0, x=0):
31    global backtracks
32    y, x = find_next_cell(grid)
33    # 終了判定
34    if y == -1 or x == -1:
35        return True
36    # 入力
37    for value in range(1, 10):
38        if is_valid(grid, y, x, value):
39            grid[y][x] = value
40            if (y,x) in clone_cells:
41                y2,x2 = clone_cells[(y,x)]
42                if is_valid(grid, y2, x2, value):
43                    grid[y2][x2] = value
44                    if solve_sudoku(grid):
45                        return True
46                    grid[y2][x2] = 0
47                    backtracks += 1
48            else:
49                if solve_sudoku(grid):
50                    return True
51            backtracks += 1
52            grid[y][x] = 0
53
54    return False