import sys
def main():
with open(sys.argv[1], 'r') as f:
s1 = f.read()
s2 = s1.split()
for i in range(len(s2)):
s2[i] = int(s2[i])
grid = [s2[i:i+9] for i in range(0, len(s2), 9)]
solve(grid,0,0)
def check(grid, r, c, k):
for i in range(9):
if grid[r][i] == k:
return False
if grid[i][c] == k:
return False
x_area = (c // 3) * 3
y_area = (r // 3) * 3
for i in range(3):
for j in range(3):
if grid[y_area + i][x_area + j] == k:
return False
return True
def solve(grid, r=0, c=0):
f = open(sys.argv[2],'w')
counter = 0
if r == 9:
return True
elif c == 9:
return solve(grid, r+1, 0)
elif grid[r][c] != 0:
return solve(grid, r, c+1)
else:
poss = []
for k in range(1, 10):
if check(grid, r, c, k):
poss.append(k)
if len(poss) == 1:
grid[r][c] = k
counter += 1
print("-" * 18, "Step " + str(counter) + " - " + str(poss[0]) + " @ " + "R" + str(r + 1) + "C" + str(c + 1), "-" * 18, sep='\n', file=f)
for x in grid:
print(" ".join(map(str, x)), file=f)
print("-" * 18, file=f)
if solve(grid, r, c+1):
return True
return False
if __name__ == "__main__":
main()
In this code i take argument like this
0 4 0 0 0 0 1 7 9
0 0 2 0 0 8 0 5 4
0 0 6 0 0 5 0 0 8
0 8 0 0 7 0 9 1 0
0 5 0 0 9 0 0 3 0
0 1 9 0 6 0 0 4 0
3 0 0 4 0 0 7 0 0
5 7 0 1 0 0 2 0 0
9 2 8 0 0 0 0 6 0
then i turn this to list for indexing. I want to check cells and if there is a cell have one possible number to put number instead of zero, put this number and print all sudoku table then repeat this steps. print steps, solve again, print steps, solve again. But in my output.txt file it prints only first step. What is wrong?
------------------
Step 1 - 8 @ R1C1
------------------
8 4 0 0 0 0 1 7 9
0 0 2 0 0 8 0 5 4
0 0 6 0 0 5 0 0 8
0 8 0 0 7 0 9 1 0
0 5 0 0 9 0 0 3 0
0 1 9 0 6 0 0 4 0
3 0 0 4 0 0 7 0 0
5 7 0 1 0 0 2 0 0
9 2 8 0 0 0 0 6 0
------------------
This is output that i want but all steps like this. I mean there are 48 zero here and it have to print 48 step.
There are a few issues:
Your output file will only have one grid, because in each call of solve, you call f = open(sys.argv[2],'w'). You should only open the file for writing once.
You don't close the output file. Because of these two points, you need to wrap the recursive calls into a top-level call that opens and closes the file.
The list poss is not of much use in the way you use it. It starts empty, and obviously after the first append it has one element, and so you place the value and make a recursive call. But this didn't really check whether the cell didn't have other solutions. Or if intended to do it the "backtracking way", if the recursion cannot solve the grid, then your code will not try an alternative. See next point.
You write "if there is a cell have one possible number to put number instead of zero", but this does not consider the case where there might be multiple possibilities for all cells that are empty (0). So that means you have to try a value, and if it doesn't lead to a solution, try an alternative, etc. If you really only want to fill cells that only have on possible value, you first need to let the k loop complete to the end, as only then you can be sure there is only one solution. And if that is not true, you should try with another cell, and not return False.
Related to this, with proper backtracking, you need to backtrack when no value can make it to a solved grid. In that case you should clear the previously placed value, just before returning False. This also means that your output file may have many more outputs then just the number of zeroes, because it will also have outputs that later on turn out to not lead to a solution.
Here is the corrected code with a backtracking solution:
def main():
with open(sys.argv[1], 'r') as f:
s1 = f.read()
s2 = s1.split()
for i in range(len(s2)):
s2[i] = int(s2[i])
grid = [s2[i:i+9] for i in range(0, len(s2), 9)]
solve(grid) # call with one argument
def check(grid, r, c, k):
for i in range(9):
if grid[r][i] == k:
return False
if grid[i][c] == k:
return False
x_area = (c // 3) * 3
y_area = (r // 3) * 3
for i in range(3):
for j in range(3):
if grid[y_area + i][x_area + j] == k:
return False
return True
def solve(grid):
f = open(sys.argv[2],'w') # Should only execute once. So not part of recursive function
counter = 0 # Should only execute once. So not part of recursion.
def recur(r, c):
nonlocal counter
if r == 9:
return True
elif c == 9:
return recur(r+1, 0)
elif grid[r][c] != 0:
return recur(r, c+1)
else:
# Don't use poss. It will prevent you from trying all available options
for k in range(1, 10):
if check(grid, r, c, k):
grid[r][c] = k
counter += 1
print("-" * 18,
"Step " + str(counter) + " - " + str(k)
+ " @ " + "R" + str(r + 1) + "C" + str(c + 1),
"-" * 18,
sep='\n', file=f)
for x in grid:
print(" ".join(map(str, x)), file=f)
print("-" * 18, file=f)
if recur(r, c+1):
return True
grid[r][c] = 0 # backtrack!
return False
result = recur(0, 0)
f.close()
return result
if __name__ == "__main__":
main()
If you are supposed to only solve cells that have just one possible value, then you better not use recursion, as there is no backtracking then. Use iteration:
Here is the code for "simple" Sudokus:
def solve(grid):
def count_empty_cells():
count = 0
for r in range(9):
for c in range(9):
if grid[r][c] == 0:
count +=1
return count
def find_cell_with_one_solution():
for r in range(9):
for c in range(9):
if grid[r][c] == 0:
poss = []
for k in range(1, 10):
if check(grid, r, c, k):
poss.append(k)
if len(poss) == 1:
return r, c, poss[0]
return None
with open(sys.argv[2], 'w') as f:
for counter in range(count_empty_cells()):
result = find_cell_with_one_solution()
if not result: # could not find an empty cell with one solution
f.close()
raise ValueError("This is not a simple Sudoku puzzle!")
r, c, k = result
grid[r][c] = k
print("-" * 18,
"Step " + str(counter+1) + " - " + str(k)
+ " @ " + "R" + str(r + 1) + "C" + str(c + 1),
"-" * 18,
sep='\n', file=f)
for x in grid:
print(" ".join(map(str, x)), file=f)
print("-" * 18, file=f)