I'm trying to implement a backtracking algorithm to solve a sudoku, but for some reason it generates duplicate values in the same row/column, which isn't allowed.
The algorithm:
from math import floor
from typing import List
class Cell:
x: int
y: int
times_visited: int = 0
value: int
is_prefilled: bool
def __init__(self, x: int, y: int, value: int):
self.x = x
self.y = y
self.value = value
self.is_prefilled = value != None
def gen_possible_for(cell: Cell, sudoku: List[List[Cell]]) -> List[int]:
# Horizontal
horizontal = sudoku[cell.y]
# Vertical
vertical = [sudoku[y][cell.x] for y in range(9)]
# 3x3 square
base_x = floor(cell.x / 3) * 3
base_y = floor(cell.y / 3) * 3
square = [
sudoku[base_y + rel_y][base_x + rel_x]
for rel_y in range(3)
for rel_x in range(3)
]
#print("H:",horizontal)
#print("V:",vertical)
#print("S:",square)
all = horizontal + vertical + square
return [v for v in range(1, 9+1) if v not in all]
def solve_sudoku(sudoku: List[List[int]]):
# Recursive backtracking algorithm
sudoku_cells = [Cell(x, y, sudoku[y][x]) for x in range(9) for y in range(9)]
i = 0
while i < len(sudoku_cells):
cell = sudoku_cells[i]
if not cell.is_prefilled:
possible_values = gen_possible_for(cell, sudoku)
if not possible_values or cell.times_visited >= len(possible_values):
if i == 0:
# Sudoku is unsolvable
return False
print("decr")
i -= 1
else:
cell.value = possible_values[cell.times_visited]
i += 1
cell.times_visited += 1
else:
i += 1
# For some reason, (x + y * 9) causes the grid to rotate 90 degrees counter-clockwise
return [[sudoku_cells[y + x * 9].value for x in range(9)] for y in range(9)]
Using the following sudoku as input:
# A sudoku from sudoku.com
sudoku = [
[None, 6, 7, None, 5, 4, None, None, None],
[1, None, None, None, None, None, 2, None, None],
[None, None, None, 6, 1, None, None, 4, None],
[None, None, None, None, None, 5, None, 6, None],
[None, 1, 2, 8, None, None, 4, None, None],
[6, None, 3, None, None, None, 8, 7, None],
[None, None, None, None, None, 7, None, 2, 3 ],
[7, 2, 9, 3, 6, None, None, 8, 4 ],
[4, None, 6, 5, 8, 2, None, 9, 1 ]
]
The output is:
2 6 7 2 5 4 1 1 8
1 3 4 7 3 3 2 3 5
2 3 5 6 1 3 3 4 5
8 4 4 1 2 5 1 6 2
5 1 2 8 3 3 4 3 5
6 4 3 1 2 1 8 7 2
5 5 1 1 4 7 5 2 3
7 2 9 3 6 1 5 8 4
4 3 6 5 8 2 7 9 1
For some odd reason it generates a lot of duplicate values, such as the 2 at (0,0) and the 2 at (0,2), the 5 at (0,4) and the 5 at (0,6) and many more. Also notice that there isn't a single decr debug message (from the print statement at line 55).
What am I doing wrong?
Thanks in advance!
The main issue is that you are only looking at the original grid to restrict values, whereas really you need to know about the trial values that you have put in your solution grid of Cells. So adjust your gen_possible_for to look at the Cells, not the original puzzle grid.
You also need to make sure that you clear Cell values as you backtrack past them, in that case, and have a way of backtracking past prefilled cells. And you need to hold the list of possible values for each cell (until you backtrack past it); if you .pop() values from this list then you don't also need to keep track of visit numbers.