10
\$\begingroup\$

This is my naive approach on implementing a Sudoku solver, which is okay for simple Sudokus like this:

puzzle = [[5,3,0,0,7,0,0,0,0],
        [6,0,0,1,9,5,0,0,0],
        [0,9,8,0,0,0,0,6,0],
        [8,0,0,0,6,0,0,0,3],
        [4,0,0,8,0,3,0,0,1],
        [7,0,0,0,2,0,0,0,6],
        [0,6,0,0,0,0,2,8,0],
        [0,0,0,4,1,9,0,0,5],
        [0,0,0,0,8,0,0,7,9]]

However, it is rather slow for hard Sudokus like this:

[[9, 0, 0, 0, 8, 0, 0, 0, 1],
 [0, 0, 0, 4, 0, 6, 0, 0, 0],
 [0, 0, 5, 0, 7, 0, 3, 0, 0],
 [0, 6, 0, 0, 0, 0, 0, 4, 0],
 [4, 0, 1, 0, 6, 0, 5, 0, 8],
 [0, 9, 0, 0, 0, 0, 0, 2, 0],
 [0, 0, 7, 0, 3, 0, 2, 0, 0],
 [0, 0, 0, 7, 0, 5, 0, 0, 0],
 [1, 0, 0, 0, 4, 0, 0, 0, 7]]

The challenge description is:

Write a function that will solve a 9x9 Sudoku puzzle. The function will take one argument consisting of the 2D puzzle array, with the value 0 representing an unknown square.

The Sudokus tested against your function will be "insane" and can have multiple solutions. The solution only needs to give one valid solution in the case of the multiple solution sodoku.

It might require some sort of brute force.

Tests: 100 random tests and 5 assertions per test

Time limit: 12sec

My code:

def sudoku(board):
    (x, y) = find_empty_cell(board)
    if (x, y) == (-1, -1):
        return True

    for i in {1,2,3,4,5,6,7,8,9}:
        if valid(x,y,i,board):
            board[x][y] = i
            if sudoku(board):
                return board
            board[x][y] = 0


def valid(x,y,n,board):
    #check row and column
    for i in range(9):
        if board[x][i] == n or board[i][y] == n:
            return False

    #check box
    new_x = x//3 * 3
    new_y = y//3 * 3
    for i in range(3):
        for j in range(3):
            if board[new_x + i][new_y + j] == n:
                return False

    return True



def find_empty_cell(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                return (i,j)

    return (-1,-1)

I am trying to succeed in passing a coding challenge in a competitive platform, which my specific code times out.

\$\endgroup\$
  • \$\begingroup\$ What is the time restriction? \$\endgroup\$ – Chris Tang May 15 at 10:32
  • \$\begingroup\$ Hey @ChrisTang it is 12 sec. I will edit my post and add the full description of it. \$\endgroup\$ – Leo oeL May 15 at 10:41
  • 1
    \$\begingroup\$ Your code doesn't take into account problems with multiple candidates for a cell, and so it'll produce a wrong answer on Hard boards. \$\endgroup\$ – Mahmoud Farouq May 15 at 11:49
  • 2
    \$\begingroup\$ codewars' Hard Sudoku Solver? \$\endgroup\$ – greybeard May 15 at 13:47
  • \$\begingroup\$ @greybeard yeap that's the one :) \$\endgroup\$ – Leo oeL May 15 at 13:49
18
\$\begingroup\$

I am going to provide a much more over-the-top strategies to deal with Sudoku rather than outright code snippets so you can try it out on your own. [Also I am avoiding code-refactor, so that you can focus on Algorithm first, and then we will talk about Code Design, and finally implementation]

However, if you need more explicit help or I am not clear enough, leave a comment, and I would provide more details as needed.

So, the first thing I noticed about your program is that you implement a simple way to select which cell to fill: Find the first empty one, and try filling that.

There is a much more efficient way to do this: find the cell which has only one Value, and fill that first, this will lead you to fill in first few digits of board pretty quickly, and constrain your solution space.

For this: Just iterate over every cell, and store it in dict what are possible values this cell can have. Naively: A Cell C can have only values which are not available in its row, its column and its box. This will lead to something like this:

A1 -- {1, 3, 5}
A2 - {1, 6}
A3 - {6}

and so on...

Now, fun fact! You found out that A3 has only one value, so you fill in that. What this means is that you can now remove 6 from A row and 3rd column as well the box, which will further give 1-value cells, and you can repeat this process till there are no 1-value cells are left.

This will give tremendous speed improvements over your current solution.

But we are not done yet!


Moving forward, there are two ways to go:

  • Improve our function which determines the values for cell. Remember, our naive function was that a cell has values which are not in row, cell and box. But in Sudoku, we apply other logics as well. For example if both A2 and A3 has value of {2, 4}, then we know that no other cell in A row can have value of 2 and 4, and we can remove it. There are several such strategies which can help you out. This is how Humans solve Sudoku

  • Next is Computer's way. Now, you already have a solution which is close to this, which is to have a backtracking mechanism. However, instead of selecting cell randomly, select a cell with least possible values to fill in the random value. For example if you have to choose between A2 which has 2 choices and A4 which has 3 possible choices, fill in A2 first.


These will result in very fast Sudoku solvers :)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Hello, @kushj will try and work on implementing what you suggested. Thank you for your time and effort :) \$\endgroup\$ – Leo oeL May 15 at 13:50
  • \$\begingroup\$ Okay so, your brilliant insight and some further research helped me make it through :) Completed the task! \$\endgroup\$ – Leo oeL May 16 at 10:15
  • 1
    \$\begingroup\$ IDK if it would help in Python, but in a compiled language without huge interpreter overhead you might use an array of integer bitmaps to implement the dictionary of sets. Removing members from the set is just bitwise AND with ~(1<<n), and you can remove multiple bits at once. You can also quickly detect a bitmap that has only a single bit set with v & (v - 1) == 0. This all works for these sets because the members are integers in the 1..9 range. Most of the bit manipulation can even be done with SIMD vectors \$\endgroup\$ – Peter Cordes May 16 at 23:48
3
\$\begingroup\$

This is a classic constraint satisfaction problem.

There are a couple of general techniques you can use to greatly speed up the search for a solution:

  • constraint propagation --- using the constraints of the game to immediately rule out possible values a variable can take; and

  • variable ordering --- being clever about deciding which variable to attempt to assign next.

In Sudoku, the variables are the cells, and the possible values are the digits, 1-9.

You may wish to use a more refined search-state representation. With your current representation, a cell is either filled in or isn't, but you might be better off keeping track of all the possible values the cell could have (initially, the set {1, 2, ..., 9}), which would allow you to incrementally rule out values.

The improved algorithm would be a backtracking search, like the one you already have, but at each node of the search tree you apply constraint propagation to immediately rule out some of the options. If you reach a state in which all of the values of a variable have been ruled out, you know the sudoku is not solvable from that state, so you backtrack.

Constraint Propagation

An inference procedure looks at the present search state, and uses knowledge of the constraints to eliminate possible assignments. You can make full use of a procedure by repeatedly applying it until it produces no change.

Here are a couple of inference procedures you might apply:

  • When the value of a cell has been deduced, you can remove that value from all other cells in the same unit (row, column, or box).

  • When two cells in a unit have been reduced to the exact same pair of possible values, you can rule those values out for all other cells in the same unit. This is known as the 'naked pairs' strategy.

There are other strategies you might want to try implementing, although you will get diminishing returns.

Variable Ordering

This one's simple: simply choose the most constrained variable first -- that is, the cell with the least options. Intuitively, this is likely to rule out bad assignments earlier, resulting in a larger portion of the search tree being pruned by backtracking.


Leave a comment if there's anything I haven't explained clearly.

You can find an excellent write-up on Sudoku solving here.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

I did this once in javascript, think the fastest algorithm was:

  • create your board
  • visit each cell, if it is empty, iterate through all possible values
  • if the board has an inconsistency, take the next value
  • if all values are used up, it cannot be solved
  • if the value is valid, go directly to the next cell

basically a depth-search-first, creating the board that will be the solution. each inconsistency only goes back one step and tries the next possible value there, so you have very little overhead for checking one scenario.

edit: okay, that is called backtracking according to wikipedia:

https://en.wikipedia.org/wiki/Sudoku_solving_algorithms<

what i think is faster than your solution:

  • you don't iterate the whole board to find the next empty cell because you already know that the previous ones are filled.

  • you can just check the "adjecent cells" (same row, same column, same box) to see if the entered value is in them. no need to check the whole board for correctness. maybe you should check it once in the beginning just to be sure the problem is not bonkers already.

okay, think i am wrong again, you already know that the values are good because you used the "adjecent cells" to calculate the possible values.

i think i wasn't even keeping the possible values as lookup table, could be too much overhead to maintain them. just read them directly fom the board. or try both and see what's faster. you want to learn coding, so trying out stuff and measuring your solutions is a very good technique.

good luck / have fun!

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.