程式

引言

這一篇對此前理論的實現，首先創建一個文件夾包含如下文件：

1
2
3
4
5
6
.
├── graph.py
├── guess.py
├── path.py
├── solve.py
└── utilities.py

下面會解釋各腳本及用法。

腳本

求解

終端python solve.py即可，如果是第一次運行，它將創建一個input.txt文件，其中未知數字用0表示，你需要將已知的數字替換掉對應位置的零。

完成後你需要再執行一次python solve.py，這次將進入求解過程，求解數獨題的中間過程會自動保存在graph.txt文件中。下次運行python solve.py時會詢問是否讀取graph.txt文件，亦或是將其覆蓋而重新創建input.txt文件以寫入數獨。

至於其他功能皆有說明，讀者可以自行嘗試。

solve.py如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
import os
from graph import Graph
from path import Path
from utilities import *
from guess import Contradiction

def solve(graph):
    print("=== Sudoku Solver Initialized ===")
    print("Loading puzzle and applying initial constraint propagation...")
    g = Graph(graph)
    g.update()
    print("\n=== Interactive Sudoku Solving Session ===")
    print("Note: This tool applies logical techniques but may not solve every puzzle.")
    print("You can manually revise 'graph.txt' and restart if necessary.")
    print("Available commands:")
    print("  'p' - Find logical paths using advanced reasoning")
    print("  'u' - Update graph using basic constraint propagation")
    print("  's' - Show current state with all candidates per cell")
    print("  'g' - Run contradiction-based guessing (eliminates candidates via contradictions)")
    print("  'l' - Show constraint propagation cancellation log")
    print("  'gl' - Show last guess (contradiction) log")
    print("  'q' - Quit and save current progress")
    
    last_guess_log = ""
    while True:
        print("\n" + "="*50)
        cmd = input("Enter command (p/u/s/g/l/gl/q): ")
        print("Saving current state to file...")
        write_graph(g.graph)
        
        if cmd == 'q':
            # Save again right before exit to guarantee latest state
            write_graph(g.graph)
            print("Session ended. Progress saved to graph.txt")            
            break
        elif cmd == 'u':
            print("\n--- Applying Constraint Propagation ---")
            g.update()
        elif cmd == 'p':
            print("\n--- Searching for Logical Paths ---")
            p = Path(g.graph)
            depth_str = input('Enter search depth (even numbers > 0, default=2): ')
            try:
                depth = int(depth_str)
                if depth > 0 and depth % 2 == 0:
                    print(f"Searching with depth {depth}...")
                    g.graph = p.find(depth)
                else:
                    print("Invalid depth. Using default depth of 2...")
                    g.graph = p.find()
            except ValueError:
                print("Using default depth of 2...")
                g.graph = p.find()
            print("Applying constraint propagation after path analysis...")
            g.update()
        elif cmd == 'g':
            print("\n--- Running Guess (Contradiction Search) ---")
            c = Contradiction(g.graph)
            new_graph = c.find()
            last_guess_log = c.log
            g.graph = new_graph
            print("Applying constraint propagation after guessing...")
            g.update()
        elif cmd == 'l':
            print("\n--- Constraint Propagation Log ---")
            if hasattr(g, 'log') and g.log:
                print(g.log)
            else:
                print("(No constraint propagation cancellations logged yet.)")
        elif cmd == 'gl':
            print("\n--- Last Guess Log ---")
            if last_guess_log:
                print(last_guess_log)
            else:
                print("(No guess log available yet.)")
        elif cmd == 's':
            print("\n--- Current Puzzle State ---")
            print_current_state(g.graph)
        else:
            print("Invalid command. Please enter 'p', 'u', 's', 'g', 'l', 'gl', or 'q'.")         
        
def main():
    print("=== Sudoku Solver - Main Menu ===")
    print("This script is a helper tool for solving Sudoku via logic.")
    print("It does not cover all cases. If it gets stuck, press 'q' to quit.")
    print("Your current progress will be saved automatically to 'graph.txt'.")
    print("You may edit 'graph.txt' manually as an intermediate step and then restart.\n")
    
    if os.path.exists(DEFAULT_INTERMEDIATE_FILE):
        print(f"Previous solving session found in '{DEFAULT_INTERMEDIATE_FILE}'")
        load_choice = input('Load previous puzzle? (y/n): ')
        if load_choice.lower() == 'y':
            print("Loading previous puzzle state...")
            graph = read_graph()
            solve(graph)
            return
        else:
            print("Starting fresh...")
    
    if os.path.exists(DEFAULT_INPUT_FILE):
        print(f"Input file '{DEFAULT_INPUT_FILE}' found.")
        print("Converting input puzzle to internal format...")
        graph = input_to_graph()
        solve(graph)
        return
    else:
        print(f"No input file '{DEFAULT_INPUT_FILE}' found.")
        print("Creating template input file...")
        set_input()
            
if __name__ == '__main__':
    main()

如果不想深入了解，那麼看到這裡即可，你只需要copy以下依賴腳本程式到對應的文件中。

接下來會對各個依賴腳本作出簡要說明。

節點

這裡將所有節點的可能狀態視為一個圖，它是後續分析的基礎。

graph.py如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
class Graph:
    def __init__(self, graph):
        self.graph = graph
        self.known_num_list = []
        self.known_num_list_update = []
        
        self.vertex_list = []
        self.neighbor_dict = {'t_patt': {}, 'f_patt': {}}
        self.path_list = []

        self.log = ''
    
    def update(self):
        print("Starting constraint propagation analysis...")
        self.update_num()
        self.update_graph()
                    
    def update_num(self):
        for i in range(9):
            for j in range(9):
                if type(self.graph[i][j]) == int:
                    if [self.graph[i][j],[i,j]] not in self.known_num_list:
                        self.known_num_list_update.append([self.graph[i][j],[i,j]])
                else:
                    if len(self.graph[i][j]) == 1:
                        if [self.graph[i][j][0],[i,j]] not in self.known_num_list:                            
                            self.known_num_list_update.append([self.graph[i][j][0],[i,j]])
                            print('  ✓ Naked Single: Found %d at row %d, column %d (only candidate remaining)' %(self.graph[i][j][0],i+1,j+1))
                    else:
                        
                        for num in self.graph[i][j]:
                            ls = []
                            for k in range(9):
                                if type(self.graph[i][k]) == list:
                                    if num in self.graph[i][k]:
                                        ls.append([num,[i,k]])
                            if len(ls) == 1:
                                self.known_num_list_update += ls
                                print('  ✓ Hidden Single (Row): Found %d at row %d, column %d (only position in row %d)' %(ls[0][0],ls[0][1][0]+1,ls[0][1][1]+1,ls[0][1][0]+1))
                                break
                                
                            ls = []
                            for k in range(9):
                                if type(self.graph[k][j]) == list:
                                    if num in self.graph[k][j]:
                                        ls.append([num,[k,j]])
                            if len(ls) == 1:
                                self.known_num_list_update += ls
                                print('  ✓ Hidden Single (Column): Found %d at row %d, column %d (only position in column %d)' %(ls[0][0],ls[0][1][0]+1,ls[0][1][1]+1,ls[0][1][1]+1))
                                break
                                
                            ls = []
                            for k in range(9):
                                for l in range(9):
                                    if k // 3 == i // 3 and l // 3 == j // 3:
                                        if type(self.graph[k][l]) == list:
                                            if num in self.graph[k][l]:
                                                ls.append([num,[k,l]])
                            if len(ls) == 1:
                                self.known_num_list_update += ls
                                block_num = (ls[0][1][0]//3)*3 + (ls[0][1][1]//3) + 1
                                print('  ✓ Hidden Single (Block): Found %d at row %d, column %d (only position in block %d)' %(ls[0][0],ls[0][1][0]+1,ls[0][1][1]+1,block_num))
                                break
        if len(self.known_num_list_update) == 0:
            print("  No new numbers found using basic techniques.")
        else:
            print(f"  Found {len(self.known_num_list_update)} new number(s) using constraint analysis.")
                                            
    def update_graph(self):
        if len(self.known_num_list_update) > 0:
            print("Propagating constraints and eliminating candidates...")
            candidates_removed = 0
                        
            for i in range(9):
                for j in range(9):
                    if type(self.graph[i][j]) == list:
                        for update_num in self.known_num_list_update:
                            num = update_num[0]
                            num_i = update_num[1][0]
                            num_j = update_num[1][1]
                            
                            if i == num_i and j != num_j:
                                if num in self.graph[i][j]:
                                    msg = (
                                        f"Confirmed {num} at row {num_i + 1} and column {num_j + 1}, "
                                        f"leading to the cancellation of {num} at row {i + 1} and column {j + 1} "
                                        f"because of the same row."
                                        )

                                    self.log += msg + '\n'
                                    self.graph[i][j].remove(num)
                                    candidates_removed += 1
                            
                            if j == num_j and i != num_i:
                                if num in self.graph[i][j]:
                                    msg = (
                                        f"Confirmed {num} at row {num_i + 1} and column {num_j + 1}, "
                                        f"leading to the cancellation of {num} at row {i + 1} and column {j + 1} "
                                        f"because of the same column."
                                        )
                                    self.log += msg + '\n'
                                    self.graph[i][j].remove(num)
                                    candidates_removed += 1
                                    
                            if i // 3 == num_i // 3 and j // 3 == num_j // 3 and i != num_i and j != num_j:
                                if num in self.graph[i][j]:
                                    msg = (
                                        f"Confirmed {num} at row {num_i + 1} and column {num_j + 1}, "
                                        f"leading to the cancellation of {num} at row {i + 1} and column {j + 1} "
                                        f"because of the same block."
                                        )
                                    self.log += msg + '\n'
                                    self.graph[i][j].remove(num)
                                    candidates_removed += 1

                            if i == num_i and j == num_j:
                                msg = (
                                    f"Confirmed {num} at row {num_i + 1} and column {num_j + 1}, "
                                    f"leading to the cancellation of other candidates at row {i + 1} and column {j + 1} "
                                    f"because of the same cell."
                                    )
                                self.log += msg + '\n'
                                self.graph[i][j] = [num]
                                    
            print(f"  Eliminated {candidates_removed} candidate(s) from affected cells.")
                                    
        self.known_num_list += self.known_num_list_update
        self.known_num_list_update = []
        print("Constraint propagation completed.")

路徑

這一部分對應此前的理論，你需要手動輸入遞歸搜索最大深度，必須是大於零的偶數。

path.py如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
class Path:
    def __init__(self, graph):
        self.graph = graph
                        
        self.vertex_list = []
        self.neighbor_dict = {'t_patt': {}, 'f_patt': {}}
        self.path_list = []
        
    def find(self, depth=2):
        print(f"Initializing graph theory analysis with search depth {depth}...")
        self.initialize_vertex()
        self.initialize_neighbor()
        self.solve(depth)
        return self.graph
        
    def initialize_vertex(self):
        self.vertex_list = []
        vertex_count = 0
        for i in range(9):
            for j in range(9):
                if type(self.graph[i][j]) == list:
                    for num in self.graph[i][j]:
                        self.vertex_list.append(''.join(str(n) for n in [i,j,num]))
                        vertex_count += 1
        print(f"  Created {vertex_count} vertices representing all candidate possibilities.")                                            
        
    def pattern_node_list(self, idx_str, patt):
        ls = []        
        i = int(idx_str[0])
        j = int(idx_str[1])
        m = int(idx_str[2])
        
        lst = []
        for n in self.graph[i][j]:            
            if n != m:
                lst.append([i,j,n])
        if patt:
            if len(lst) == 1:
                ls += lst
        else:
            ls += lst
        
        lst = []        
        for k in range(9):
            if k != j:
                if type(self.graph[i][k]) == list:
                    if m in self.graph[i][k]:
                        lst.append([i,k,m])
        if patt:
            if len(lst) == 1:
                ls += lst
        else:
            ls += lst
        
        lst = []    
        for k in range(9):
            if k != i:
                if type(self.graph[k][j]) == list:
                    if m in self.graph[k][j]:
                        lst.append([k,j,m])
        if patt:
            if len(lst) == 1:
                ls += lst
        else:
            ls += lst
        
        lst = []                
        for k in range(9):
            for l in range(9):
                if k // 3 == i // 3 and l // 3 == j // 3:
                    if k != i or l != j:
                        if type(self.graph[k][l]) == list:
                            if m in self.graph[k][l]:                                
                                lst.append([k,l,m])
        if patt:
            if len(lst) == 1:
                if lst[0] not in ls:
                    ls += lst
        else:
            for item in lst:
                if item not in ls:
                    ls.append(item)
                    
        ls_str = []
        for item in ls:
            idx_str_gen = ''.join(str(n) for n in item)
            ls_str.append(idx_str_gen) 
        return ls_str
   
    def initialize_neighbor(self):
        self.neighbor_dict = {'t_patt': {}, 'f_patt': {}}
        for idx_str in self.vertex_list:
            self.neighbor_dict['t_patt'][idx_str] = self.pattern_node_list(idx_str, True)    
            self.neighbor_dict['f_patt'][idx_str] = self.pattern_node_list(idx_str, False)    
        print(f"  Built neighbor relationships for {len(self.vertex_list)} vertices (true/false patterns).")
                                                                                                                                                                          
    def search_cycle(self, orig, idx_str, patt, depth=2):
        if patt:
            neighbor_ls = self.neighbor_dict['t_patt'][idx_str]
        else:
            neighbor_ls = self.neighbor_dict['f_patt'][idx_str]    
        
        if depth % 2 == 0:                                        
            if orig in neighbor_ls:
                self.path_list.append(orig)                                                
                return True  
        if depth == 0:  
            return False          
        for neighbor in neighbor_ls:                
            if self.search_cycle(orig, neighbor, not patt, depth-1):
                self.path_list.append(neighbor)
                return True
                            
    def solve(self, depth=2):
        print(f"Searching for logical paths and contradictions...")
        paths_found = 0
        confirmations = 0
        eliminations = 0
        
        for idx_str in self.vertex_list:            
            path_str = '\n  🔍 Analyzing path for candidate %s at row %d, column %d:' % (idx_str[2], int(idx_str[0])+1, int(idx_str[1])+1)
                      
            if self.search_cycle(idx_str, idx_str, True, depth):
                paths_found += 1
                confirmations += 1
                for item in list(reversed(self.path_list)):
                    path_str += ' → %s[%d,%d]' % (item[2], int(item[0])+1, int(item[1])+1)
                print(path_str)                
                print('    ✓ CONFIRMED: Candidate %s at row %d, column %d (logical path found)' %(idx_str[2], int(idx_str[0])+1,int(idx_str[1])+1))
                self.path_list = []  
                
                self.graph[int(idx_str[0])][int(idx_str[1])] = [int(idx_str[2])]
                
            elif self.search_cycle(idx_str, idx_str, False, depth):
                paths_found += 1
                eliminations += 1
                for item in list(reversed(self.path_list)):
                    path_str += ' → %s[%d,%d]' % (item[2], int(item[0])+1, int(item[1])+1)
                print(path_str)                
                print('    ✗ ELIMINATED: Candidate %s at row %d, column %d (contradiction found)' %(idx_str[2], int(idx_str[0])+1,int(idx_str[1])+1))
                self.path_list = []  
                
                self.graph[int(idx_str[0])][int(idx_str[1])].remove(int(idx_str[2]))
                
        if paths_found == 0:
            print("  No logical paths found at current depth. Try increasing depth or use constraint propagation.")
        else:
            print(f"Path analysis completed: {confirmations} confirmations, {eliminations} eliminations.")

歸謬

對於困難的數獨，僅僅依靠路徑搜索是不夠的，這時候需要假設一個候選數成立，接著判斷是否會導致矛盾的結果以便刪去該候選數。我對這種處理方式並不滿意，這僅僅是一個權宜之計，在文章的最後會作出解釋。

guess.py如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
from copy import deepcopy
from graph import Graph

class Contradiction(Graph):
    def __init__(self, graph):
        Graph.__init__(self, graph)
        self.original_graph = deepcopy(graph)
    
    def if_contradict(self):
        # Check empty cells
        for i in range(9):
            for j in range(9):
                if type(self.graph[i][j]) == list:
                    if len(self.graph[i][j]) == 0:
                        msg = 'Contradiction: cell at row %d, column %d has no candidates.' % (i+1, j+1)
                        self.log += msg + '\n'
                        print(msg)
                        return True
        # Check rows
        for i in range(9):
            present_digits = []
            for j in range(9):
                if type(self.graph[i][j]) == list:
                    for cand in self.graph[i][j]:
                        if cand not in present_digits:
                            present_digits.append(cand)
                else:
                    if self.graph[i][j] not in present_digits:
                        present_digits.append(self.graph[i][j])
            for num in range(9):
                if num+1 not in present_digits:
                    msg = 'Contradiction: digit %d cannot be placed anywhere in row %d.' % (num+1, i+1)
                    self.log += msg + '\n'
                    print(msg)
                    return True

        # Check columns
        for j in range(9):
            present_digits = []
            for i in range(9):
                if type(self.graph[i][j]) == list:
                    for cand in self.graph[i][j]:
                        if cand not in present_digits:
                            present_digits.append(cand)
                else:
                    if self.graph[i][j] not in present_digits:
                        present_digits.append(self.graph[i][j])
            for num in range(9):
                if num+1 not in present_digits:
                    msg = 'Contradiction: digit %d cannot be placed anywhere in column %d.' % (num+1, j+1)
                    self.log += msg + '\n'
                    print(msg)
                    return True

        # Check blocks
        for i in range(3):
            for j in range(3):
                present_digits = []
                for dr in range(3):
                    for dc in range(3):
                        r = i*3 + dr
                        c = j*3 + dc
                        if type(self.graph[r][c]) == list:
                            for cand in self.graph[r][c]:
                                if cand not in present_digits:
                                    present_digits.append(cand)
                        else:
                            if self.graph[r][c] not in present_digits:
                                present_digits.append(self.graph[r][c])
                for num in range(9):
                    if num+1 not in present_digits:
                        block_num = i*3 + j + 1
                        msg = 'Contradiction: digit %d cannot be placed anywhere in block %d.' % (num+1, block_num)
                        self.log += msg + '\n'
                        print(msg)
                        return True

        return False

    def dive(self, current_graph):
        cg = deepcopy(current_graph)
        self.update()
        
        if self.if_contradict():
            return True
        else:
            if self.graph == cg:
                return False
        
        if self.dive(self.graph):
            return True
        else:
            return False


    def find(self):
        for i in range(9):
            for j in range(9):
                if type(self.original_graph[i][j]) == list:
                    if len(self.original_graph[i][j]) > 1:

                        for k in self.graph[i][j]:
                            self.graph = deepcopy(self.original_graph)

                            msg = 'Trying candidate %d at row %d, column %d...' % (k, i+1, j+1)
                            self.log = msg + '\n'
                            print(msg)

                            self.graph[i][j] = [k]
                            if self.dive(self.graph):
                                print('Contradiction found during trial. Log:')
                                print(self.log)
                                print('Eliminating candidate %d at row %d, column %d.' % (k, i+1, j+1))
                                self.original_graph[i][j].remove(k)
                                return self.original_graph
                            

        print('No contradictions found via guessing; no eliminations made.')
        return self.original_graph

依賴

最後是一些常用的函數，這部分不需要作過多解釋。

utilities.py如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
DEFAULT_INPUT_FILE = 'input.txt'
DEFAULT_INTERMEDIATE_FILE = 'graph.txt'

def set_input():
    print(f"=== Input File Setup ===")
    print(f"This will create/overwrite '{DEFAULT_INPUT_FILE}' with a blank sudoku template.")
    k = input("Continue? (y/n): ")
    if k.lower() == 'y':
        line = ('0' + ' '*11)*9 + '\n'
        with open(DEFAULT_INPUT_FILE, 'w') as f:
            f.write(line*9)
        print(f"✓ Created template file '{DEFAULT_INPUT_FILE}'")
        print("  Replace zeros with known numbers (1-9) and save the file.")
        print("  Then restart the solver to begin solving your puzzle.")
    else:
        print("Setup cancelled.")
    
def input_to_graph():
    graph = []
    with open(DEFAULT_INPUT_FILE, 'r') as f:
        lines = f.readlines()
    for line in lines:
        ls = []
        for item in line.split():
            if item == '0':
                ls.append([1, 2, 3, 4, 5, 6, 7, 8, 9])
            else:
                ls.append(int(item))
        graph.append(ls)
    print('Done.')
    return graph
                
def read_graph():
    graph = []        
    with open(DEFAULT_INTERMEDIATE_FILE, 'r') as f:
        lines = f.readlines()
    for line in lines:
        ls = []
        for item in line.split():
            if item.startswith('['):
                ls.append([int(n) for n in item[1:-1]])
            else:
                ls.append(int(item))
        graph.append(ls)
    print('Done.')
    return graph

def write_graph(graph):
    with open(DEFAULT_INTERMEDIATE_FILE, 'w') as f:
        for line in graph:
            for item in line:
                if type(item) == list:
                    item_str = str(item).replace(', ', '')
                    item_str += (12-len(item_str))*' '
                else:
                    item_str = str(item) + ' '*11
                f.write(item_str)
            f.write('\n')

def print_current_state(graph):
    """Print current state showing all possibilities in each cell in a 3x3 grid format.
    For each cell:
      - If determined (int), the number is centered in a 9-character field.
      - If undetermined (list), display a 3x3 mini-grid of candidates (1..9 positions).
    """
    print("\nCurrent puzzle state with all possibilities:")

    # Helper to print horizontal separators between rows and blocks
    def print_row_separator(row_idx):
        # Lighter separator between regular rows, thicker between 3x3 blocks
        sep_char = '-' if (row_idx % 3 != 2) else '='
        print(sep_char * 92)

    for row in range(9):
        # Each sudoku row is rendered as 3 text lines
        row_lines = ["", "", ""]

        for col in range(9):
            # Determine possibilities for this cell
            cell_possibilities = []
            determined = False

            cell = graph[row][col]
            if isinstance(cell, int):
                cell_possibilities = [cell]
                determined = True
            else:
                # It's a list of candidates
                cell_possibilities = sorted(cell)

            if determined:
                # Center the determined number in a 9-character space
                row_lines[0] += " " * 9
                row_lines[1] += str(cell_possibilities[0]).center(9)
                row_lines[2] += " " * 9
            else:
                # Create 3x3 grid for possibilities
                grid = [[" ", " ", " "] for _ in range(3)]
                for num in cell_possibilities:
                    if 1 <= num <= 9:
                        r_idx = (num - 1) // 3  # 1,2,3 -> 0; 4,5,6 -> 1; 7,8,9 -> 2
                        c_idx = (num - 1) % 3   # 1,4,7 -> 0; 2,5,8 -> 1; 3,6,9 -> 2
                        grid[r_idx][c_idx] = str(num)

                # Convert grid rows to a more compact string (no commas, minimal spaces)
                for i in range(3):
                    compact_row = ' '.join(n if n.strip() else ' ' for n in grid[i])
                    row_lines[i] += compact_row.center(9)

            # Add vertical separator between cells and 3x3 blocks
            for i in range(3):
                row_lines[i] += '|' if (col % 3 != 2) else '||'

        # Print the three lines for this row of cells
        print("\n".join(row_lines))

        # Add horizontal separator between rows
        print_row_separator(row)

後記

以上程式可以解決絕大部分困難數獨題。我不滿意的原因是沒有考慮複雜的並聯情況，譬如下面的例子：

考慮1，2，3三個候選數只能填入同一行/列/宮的三個格子$A,B,C$，同時$C$還有額外的候選數4，那麼4應該排除掉。考慮如下形式和記號，例如
$$
C^4 \to \neg C^{12} \to (AB)^{12} \to \neg (AB)^3 \to C^3 \neg C^4
$$
其中
$$
C^{12} = C^1 \lor C^2
$$
以及
$$
(AB)^{12} = (A^1 \land B^2) \lor (A^2 \land B^1)
$$
還有
$$
(AB)^3 = A^3 \lor B^3
$$
這樣可以簡便處理並聯關係，雖然不常出現。

當然還有更加複雜的情況，我希望找到統一的簡單規則以便處理所有複雜問題，而複雜性本身僅僅在於簡單規則的耦合與疊加方式。如果以後有時間再作討論。