So, I'm still working on my Sudoku app and still having some issues, though it's making slow but steady progress!
I'm now trying to get to one of the last stages - solving sudokus. I've found SO MANY places online that talk about it in different languages, but none for LC
I tried to code it myself and it's just not working for some silly reason, so I found one that's coded in Python that looks like it works and everything, but I can't quite figure out how to convert it over to LC (I keep getting a recursion error when I try )
The code in Python is as follows:
Code: Select all
#A function to check if the grid is full
def checkGrid(grid):
for row in range(0,9):
for col in range(0,9):
if grid[row][col]==0:
return False
#We have a complete grid!
return True
#A backtracking/recursive function to check all possible combinations of numbers until a solution is found
def solveGrid(grid):
#Find next empty cell
for i in range(0,81):
row=i//9
col=i%9
if grid[row][col]==0:
for value in range (1,10):
#Check that this value has not already be used on this row
if not(value in grid[row]):
#Check that this value has not already be used on this column
if not value in (grid[0][col],grid[1][col],grid[2][col],grid[3][col],grid[4][col],grid[5][col],grid[6][col],grid[7][col],grid[8][col]):
#Identify which of the 9 squares we are working on
square=[]
if row<3:
if col<3:
square=[grid[i][0:3] for i in range(0,3)]
elif col<6:
square=[grid[i][3:6] for i in range(0,3)]
else:
square=[grid[i][6:9] for i in range(0,3)]
elif row<6:
if col<3:
square=[grid[i][0:3] for i in range(3,6)]
elif col<6:
square=[grid[i][3:6] for i in range(3,6)]
else:
square=[grid[i][6:9] for i in range(3,6)]
else:
if col<3:
square=[grid[i][0:3] for i in range(6,9)]
elif col<6:
square=[grid[i][3:6] for i in range(6,9)]
else:
square=[grid[i][6:9] for i in range(6,9)]
#Check that this value has not already be used on this 3x3 square
if not value in (square[0] + square[1] + square[2]):
grid[row][col]=value
myPen.clear()
drawGrid(grid)
myPen.getscreen().update()
if checkGrid(grid):
print("Grid Complete and Checked")
return True
else:
if solveGrid(grid):
return True
break
print("Backtrack")
grid[row][col]=0
I have some of it working, but for some reason there's an issue with the repeat. I keep getting a recursive error when I run it
For reference, this is the code I have at the moment (ignore how bad it is, it's 3AM for me at the moment and I can't even think clearly right now ), In my code, the CellTracker variable is used to keep track of the cells of the sudoku, while the TestCellTracker is used to keep track of the possible solution.
Code: Select all
global CellTracker
global TestCellTracker
global Solved
on mouseUp
put 0 into Solved
put CellTracker into TestCellTracker
SolveGrid
answer "DONE"
end mouseUp
on SolveGrid
repeat with i=1 to 81
put (trunc(i/9)+1) into Row
put i mod 9 into Col
if Col=0 then
put 9 into Col
end if
put "R"&Row&"C"&Col into Cell
if TestCellTracker[Cell]["Normal"]=0 then
put WorkOutValues(Row,Col) into Values
repeat with m=1 to 9
if Values[m]=0 then
put m into TestCellTracker[Cell]["Normal"]
exit repeat
end if
end repeat
if CheckGrid=True then
put 1 into Solved
exit repeat
else
SolveGrid
end if
end if
if Solved=0 then
put 0 into TestCellTracker[Cell]["Normal"]
end if
end repeat
end SolveGrid
function CheckGrid
repeat with i=1 to 9
repeat with j=1 to 9
if TestCellTracker["R"&i&"C"&j]["Normal"] = 0 then
return false
else
return true
end if
end repeat
end repeat
end CheckGrid
function WorkOutValues i, j
repeat with m=i to 9
put 0 into ValueCheck[m]
end repeat
repeat with m=1 to 9
if TestCellTracker["R"&i&"C"&m]["Normal"]<>0 then
put TestCellTracker["R"&i&"C"&m]["Normal"] into ValueCheck[TestCellTracker["R"&i&"C"&m]["Normal"]]
end if
if TestCellTracker["R"&m&"C"&j]["Normal"]<>0 then
put TestCellTracker["R"&m&"C"&j]["Normal"] into ValueCheck[TestCellTracker["R"&m&"C"&j]["Normal"]]
end if
end repeat
if i<=3 then
put 3 into MaxRow
if j<=3 then
put 3 into MaxCol
else if j<=6 then
put 6 into MaxCol
else
put 9 into MaxCol
end if
else if i<=6 then
put 6 into MaxRow
if j<=3 then
put 3 into MaxCol
else if j<=6 then
put 6 into MaxCol
else
put 9 into MaxCol
end if
else
put 9 into MaxRow
if j<=3 then
put 3 into MaxCol
else if j<=6 then
put 6 into MaxCol
else
put 9 into MaxCol
end if
end if
repeat with m=MaxRow-2 to MaxRow
repeat with n=MaxCol-2 to MaxCol
if TestCellTracker["R"&m&"C"&n]["Normal"]<>0 then
put TestCellTracker["R"&m&"C"&n]["Normal"] into ValueCheck[TestCellTracker["R"&m&"C"&n]["Normal"]]
end if
end repeat
end repeat
-- if sum(ValueCheck)=45 then
-- return 0
-- else
return ValueCheck
--end if
end WorkOutValues
Many thanks!