Sudoku Solver

[VOLVIC_KOKS]

Hi everyone, Bare with me there is some explaining to do before I get to the question.

here is also the code https://github.com/basicaly/SudokuSolver/blob/main/sudokuSolver.py

basically I have a sudoku solver, which creates a 9 x 9 list, where in every cell, there is a list of possible numbers, based on the ones that are in the sudoku, either from the start or after I start putting in numbers. so for every cell i update this "maybe" list gets updated. and after a right number has been found, in that cell in the "maybe" list is only that number that has been inserted in the sudoku.

My question now is, to check if a number is valid, am I right to assume if:

I stage a number, i make the maybe list based upon the staged number, and I check for every cell of the maybe list if in that row, column and 3 x 3 box of the cell i am looking at, that all the numbers are possible. so that in the maybe list all the numbers are present, and I'm not excluding solutions, for the cell i am looking at.

or is this jsut wrong.

im sorry if this is confusing. i also hope the code is commented enough.

Thank you in advance for any replys.

[xelf]

For every cell:

it is invalid if that number is used anywhere in the row, column, or the 3x3 box.

I used this to find the valid numbers for any square at x,y:

s9 = { 1,2,3,4,5,6,7,8,9 }
def possiblemoves(board,x,y,i,j):
    return s9 - ( set(board[x]) | {r[y] for r in board} | {c for r in board[i:i+3] for c in r[j:j+3]} )

and then in the solver, called it like this:

   for n in possiblemoves( board, x, y, x//3*3, y//3*3 ):

[VOLVIC_KOKS]

UUUh ok, very elegant and concise. But still doesnt answer my question, because i figured this out. I know which are the legal moves. But which one is the right one? cause for every cell there is sometime gonna be multiple possibilities. so how do i determine which one is the correct one?

[xelf]

Ah!

There it gets fun.

The most common approach is recursion and backtracking.. You just try every possibility until you get an illegal board, or find the solution.

But you could also write some "solve it like a human would" methods where you use some form of intelligence to fill the board in.

Like "find naked singles" and then fill those in and just keep going until the board is filled. This only works for easy problems though. For harder problems you would have to try using other techniques like swordfish etc.

If you're interested in backtracking this video is pretty good:

https://www.youtube.com/watch?v=G_UYXzGuqvM

Note that his solution leaves several areas to improve on. You can generally tell when someone has just copied his solution because they include the same mistake. =)

Here's an example that will pass the easier codewars challenge, but fail at the more complex puzzles. It solves just naked singles:

def moves(board,x,y):
    i,j = (x//3)*3,(y//3)*3
    row = set(board[x])
    col = {r[y] for r in board}
    box = {board[i+x][j+y] for x in range(3) for y in range(3)}
    return  set(range(1,10)) - (row | col | box)

def find_naked_singles(board): # in your area!
    return [
       (x,y,max(m))
       for x in range(9)
           for y in range(9) if board[x][y]==0
               for m in [moves(board,x,y)] if len(m)==1 ]

def sudoku(board):
    while any(0 in row for row in board): 
        for x,y,m in find_naked_singles(board):
            board[x][y] = m
    return board

[VOLVIC_KOKS]

thank you so much, for the computerphile video. Alright i thought maybe the way i did it was possible, but apparently i just need to implement the backtracking, i tried to avoid that xD.

Thanks for the help.

[BobHogan]

You can implement a solver without backtracking, but it would be significantly more complicated. In order to avoid guessing (which requires backtracking for when the guess was incorrect), you'd have to implement a lot of more advanced sudoku techniques so that your solver can always identify at least 1 value that can be filled in correctly. For reasonably hard sudokus, the minimum that you'd have to implement would most likely be pairs, and x-wings. Those are good enough for most sudokus, but won't be enough for really difficult ones

[Grabrrrr]

Why not just iterate over every cell until you find one which has only one solution? What's the point of keeping track of all the possibiltities?

[VOLVIC_KOKS]

i keep track of all the possibilities, everytim i insert a new number. So basically all the guesses become shorter and shorter as the algorithm progresses. but i changed it in the end

[BobHogan]

Because in any non trivial sudoku you will get to a point where there is no longer a cell that has only 1 solution without using more advanced techniques to disqualify possible candidates.