+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: General Coding Help (https://python-forum.io/forum-8.html)
+--- Thread: Trouble with Sudoku Solver (/thread-25686.html)
Trouble with Sudoku Solver - Techmokid - Apr-08-2020
Hello!
I got bored and decided to make a simple sudoku solver, but I am having a tiny issue wrapping my head around a simple problem.
puzzle = [["3"," "," ", "8"," ","1", " "," ","2"],
["2"," ","1", " ","3"," ", "6"," ","4"],
[" "," "," ", "2"," ","4", " "," "," "],
["8"," ","9", " "," "," ", "1"," ","6"],
[" ","6"," ", " "," "," ", " ","5"," "],
["7"," ","2", " "," "," ", "4"," ","9"],
[" "," "," ", "5"," ","9", " "," "," "],
["9"," ","4", " ","8"," ", "7"," ","5"],
["6"," "," ", "1"," ","7", " "," ","3"]
]
def isValid():
#This just scans the puzzle to see if it is valid or not by scanning for double ups of numbers in rows or columns
y = 0
while (y < 9):
detectedNumbers = []
x = 0
while(x < 9):
if (puzzle[y][x] != " "):
if (puzzle[y][x] in str(detectedNumbers)):
return False
detectedNumbers.append(puzzle[y][x])
x += 1
y += 1
y = 0
while (y < 9):
detectedNumbers = []
x = 0
while(x < 9):
if (puzzle[x][y] != " "):
if (puzzle[x][y] in str(detectedNumbers)):
return False
detectedNumbers.append(puzzle[x][y])
x += 1
y += 1
return True
def getAllConflictingSquares(x_start,y_start):
result = []
#Get all conflicting horizontal lines
x = 0
while(x < 9):
if (puzzle[y_start][x] != " "):
result.append(puzzle[y_start][x])
x += 1
#Get all conflicting vertical lines
y = 0
while(y < 9):
if (puzzle[y][x_start] != " "):
result.append(puzzle[y][x_start])
y += 1
result.sort()
return list(dict.fromkeys(result))
if (isValid() == False):
print("ERROR: NOT A VALID PUZZLE!")
quit()
#should return "1,2,3,6,7,8,9" missing out "4,5"
print(getAllConflictingSquares(1,0))
#We know we have a valid file. Now actually start solving it!
x_question = 0
y_question = 0
while (y_question < 9):
while(x_question < 9):
possibleSolutions = [1,2,3,4,5,6,7,8,9]
x_question += 1
y_question += 1I know that this isn't the most efficient code, but I just want it to work. This is still a WIP, but the issue I'm facing is in function getAllConflictingSquares(). It can correctly identify all conflicting squares in the x and y axis, but the issue I'm having trouble with is boxes. For those who haven't played sudoku, the idea is that you have to solve the puzzle by finding a number for every single position on the 9x9 board (Numbers 1 through to 9), but where there are no conflicts. A conflict arises where a number appears twice in a row, twice in a column, or twice in a box (3x3 square of positions). It the boxes I'm struggling with. It's not even a hard problem, I've just hit a mental block.Could someone help me get my head around how to find conflicts in the 3x3 square? It's not urgent, simply a project I'm doing for fun
Edit: I've finished most of the code now. It's just that one problem. The change I made was the while loops at the end. I fixed them up:
#We know we have a valid file. Now actually start solving it!
x_question = 0
y_question = 0
while (y_question < 9):
while(x_question < 9):
if (puzzle[y_question][x_question] == " "):
conflict = getAllConflictingSquares(x_question,y_question)
possibleSolutions = list({'1','2','3','4','5','6','7','8','9'} - set(conflict))
if (len(possibleSolutions) == 0):
print("No possible solutions error!")
quit()
elif (len(possibleSolutions) == 1):
print("SOLVED SQUARE")
puzzle[y_question][x_question] = str(possibleSolutions[0])
x_question = -1 #We want x_question to be equal to 0. SO, we set it to -1 so that on the next loop around it adds 1 and sets it to 0.
y_question = 0
x_question += 1
x_question = 0
y_question += 1
print("INCOMPLETE SECTION ERROR: This sudoku contains squares that result in 2 or more solutions after all other squares have been solved. This section of code is NOT complete!")
RE: Trouble with Sudoku Solver - Mateusz - Apr-08-2020
Quote:Simple is better than complex
puzzle = [["3"," "," ", "8"," ","1", " "," ","2"],
["2"," ","1", " ","3"," ", "6"," ","4"],
[" "," "," ", "2"," ","4", " "," "," "],
["8"," ","9", " "," "," ", "1"," ","6"],
[" ","6"," ", " "," "," ", " ","5"," "],
["7"," ","2", " "," "," ", "4"," ","9"],
[" "," "," ", "5"," ","9", " "," "," "],
["9"," ","4", " ","8"," ", "7"," ","5"],
["6"," "," ", "1"," ","7", " "," ","3"]
]
sq1 = [*puzzle[0][:3],*puzzle[1][:3],*puzzle[2][:3]]
# sq1 - sq9 similarly
print(sq1)
def has_duplication(square):
# remove empty ' '
to_check = [_ for _ in square if _ != ' ']
return len(to_check) != len(list(set(to_check)))
print(has_duplication(sq1))
RE: Trouble with Sudoku Solver - Techmokid - Apr-08-2020
Thankyou so much Mateusz! That was exactly what I was looking for! From here I can find out which square the requested cell is in, and just return the result of that square.
The code for each square's contents as expanded from Mateusz's code:
sq1 = [*puzzle[0][:3],*puzzle[1][:3],*puzzle[2][:3]]
sq2 = [*puzzle[0][3:6],*puzzle[1][3:6],*puzzle[2][3:6]]
sq3 = [*puzzle[0][6:9],*puzzle[1][6:9],*puzzle[2][6:9]]
sq4 = [*puzzle[3][:3],*puzzle[4][:3],*puzzle[5][:3]]
sq5 = [*puzzle[3][3:6],*puzzle[4][3:6],*puzzle[5][3:6]]
sq6 = [*puzzle[3][6:9],*puzzle[4][6:9],*puzzle[5][6:9]]
sq7 = [*puzzle[6][:3],*puzzle[7][:3],*puzzle[8][:3]]
sq8 = [*puzzle[6][3:6],*puzzle[7][3:6],*puzzle[8][3:6]]
sq9 = [*puzzle[6][6:9],*puzzle[7][6:9],*puzzle[8][6:9]]Just find out which square it's in, and problem solved!