Python Forum
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Trouble with Sudoku Solver
#1
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 += 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:
#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!")
Reply
#2
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))
Reply
#3
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!
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Sudoku Solver in Python - Can someone explain this code ? qwemx 6 2,059 Jun-27-2022, 12:46 PM
Last Post: deanhystad
  Sudoku Solver, please help to solve a problem. AdithyaR 5 2,044 Oct-28-2021, 03:15 PM
Last Post: deanhystad
  building a sudoku solver usercat123 7 2,693 Oct-01-2021, 08:57 PM
Last Post: deanhystad
  unable to use result of solver in another function ross1993hall 0 1,381 Aug-10-2020, 10:29 AM
Last Post: ross1993hall
  Help with sudoku Mondata 4 2,163 Apr-13-2020, 12:35 AM
Last Post: deanhystad
  editing lists / sudoku solver monagro 5 3,984 May-29-2018, 02:16 PM
Last Post: monagro
  Word Search Solver PythonLamer 4 5,119 Oct-12-2017, 06:13 PM
Last Post: nilamo
  Need help designing a multi-threaded solver 4Dummies 8 5,958 Jun-18-2017, 08:39 PM
Last Post: 4Dummies

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020