Bookmark and Share

Solving sudoku using PostgreSQL PL/pgSQL

Posted: Wednesday, August 19th, 2009 at 3:09 pmUpdated: Wednesday, August 19th, 2009 at 3:25 pm

Brute force sudoku solver algorithm

I’ll be using brute force method in solving the sudoku. The algorithm is outlined as below:

  1. Loop through all the cell starting at cell (1, 1)
  2. Check the value of current cell
  3. If it’s not empty, Go on to the next cell
  4. If it’s empty, find the first legal value for it
  5. If it can’t find any legal values, that means that the previous cell may have been assigned the wrong value.
  6. Track back to the previous cell that was assigned value at step 5. Delete the value.
  7. Repeat step 4 for the next value

Walking through the algorithm by hand

To make sure that my dear reader understand the algorithm, I’ll attempt to visualize it as a series of pictures below.

  1. Here is our initial sudoku puzzle.
    sudoku problem
  2. We start from cell (1, 1) then continue to (1, 2) until we reach cell (9, 9) as indicated by the green arrow.
    sudoku_cell_direction
  3. For cell (1, 1) the legal values are 2, 6, 8. Assign the first possible value 2 to cell (1, 1)
    sudoku_cell_1x1
  4. We go on to the next cell (1, 2). Currently, the only possible value is 6.
    sudoku_cell_1x2
  5. The next cells (1, 3) and (1,4) already has values. So we skip to cell (1, 5). It turned out that there’s no legal value can be assigned to it. So we track back to the previous cell we assigned value; cell (1, 2).
    sudoku_cell_1x2_revisit
  6. Since cell (1, 2) was previously assigned value 6, we need to find another legal value other than 6. Since there’s no other legal value for cell (1, 2), we need to track back to the previous cell we assigned value; cell (1, 1).
    sudoku_cell_1x1_revisit
  7. Since cell (1, 1) was previously assigned value 2, we need to find another legal value other than 2. The next value we can assign is 6.
  8. We go on to the next cell (1, 2). Currently, the only possible value is 2.
  9. We go on to the next cell (1, 5). Once again, we could not find any legal values. So we track back.
  10. The algorithm repeats until we finally reach cell (9.9).

By now, I hope you understand the algorithm. On the next page, we’ll write it out as PostgreSQL PL/pgSQL function.

Pages: 1 2 3 4

4 Responses to “Solving sudoku using PostgreSQL PL/pgSQL”

  1. WildWezyr Says:

    It seems that your solution is very slow. I\’ve executed it to find solution for Easter Monster and it is now running for over 2 660 seconds with no result :-(.

    For comparison: my old JavaScript solution yields result after 4 seconds on Chrome 4. Look could at it here: http://wildwezyr-sudoku-solver.blogspot.com/

    To facilitate population of sudoku table before execution of your code, I use this function:

    CREATE OR REPLACE FUNCTION func_full_solve_sudoku(input_data text)
    RETURNS varchar(81) as
    $BODY$DECLARE
    x int;
    y int;
    inp varchar(81);
    d int;
    c varchar(1);
    BEGIN
    inp := regexp_replace(regexp_replace(input_data, \'[\\n\\r]\’, \’\’, \’g\’), \'[^1-9]\’, \’ \’, \’g\’);

    truncate table sudoku;

    for y in 0..8 loop
    for x in 0..8 loop
    d := null;
    c := substring(inp, y * 9 + x + 1, 1);
    if c is not null and length(c) = 1 and c <> \’ \’ then d := cast(c as int); end if;
    if d is not null then
    insert into sudoku (x_col, y_col, val, is_permanent) values (y + 1, x + 1, d, true);
    end if;
    end loop;
    end loop;

    perform func_solve_sudoku();

    inp := \’\’;

    for y in 0..8 loop
    for x in 0..8 loop
    select cast(val as varchar(1)) into c from sudoku where x_col = y + 1 and y_col = x + 1;
    inp := inp || coalesce(c, \’?\’);
    end loop;
    end loop;

    return inp;
    END;$BODY$
    LANGUAGE \’plpgsql\’ VOLATILE;

    Then for Easter Monster I just run:

    select func_full_solve_sudoku(\’1…….2.9.4…5…6…7…5.9.3…….7…….85..4.7…..6…3…9.8…2…..1\’)

    If you want to see how is my solution performing for this puzzle, use this matrix

    1…….2
    .9.4…5.
    ..6…7..
    .5.9.3…
    ….7….
    …85..4.
    7…..6..
    .3…9.8.
    ..2…..1

    in textarea on the left and click [import->] and then [solve].

  2. WildWezyr Says:

    This is my second comment (first is still awaiting moderation): take a look at this: sudoku solver in just one select statement:

    http://wiki.postgresql.org/wiki/Sudoku_puzzle

    it is PostgreSQL select query and is quite fast – 120 seconds for Easter Monster compared to 4 seconds of my JavaScript solver and indeterminate amount of time of yours ;-).

  3. Maresa Says:

    Yeah .. it is actually very slow. The link that you sent uses the new WITH RECURSIVE support of PostgreSQL 8.4 which was released after my posting.

  4. WildWezyr Says:

    @Maresa: additional pl/pgsql language constructs may lead to shorter solutions, but not that huge difference in terms of efficiency. you could do the same algorithm as with “WITH RECURSIVE” using plain old postgres functions and it should work aproximately as good as single query or even better.

Leave a Reply

Time limit is exhausted. Please reload the CAPTCHA.