Trouble with Sudoku Solver

[Techmokid]

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.

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

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 += 1

I 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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

#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!")

[Mateusz]

Simple is better than complex

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

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))

[Techmokid]

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:

1 2 3 4 5 6 7 8 9 10 11

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!