Solving sudoku using PostgreSQL PL/pgSQL

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

Determining valid values for a given cell

A valid value for a given sudoku cell is values that are absent in the row, column and the block where the cell belongs. Any values that exist in those 3 regions are forbidden values. To illustrate the 3 regions, please refer to the picture below for cell (1, 1).

• Forbidden values row is highlighted with green
• Forbidden values column is highlighted with yellow
• Forbidden values for the block is highlighted with red sudoku forbidden value regions

Looking at the picture above, for cell (1, 1) the forbidden values are 1, 3, 4. 5. 7, 9; thus the allowable values for cell (1, 1) are 2, 6 and 8. To get the allowable values in SQL, we’ll need to get all legal values and remove forbidden values. We can use LEFT JOIN to achieve it.

SELECT nums.* FROM
nums
LEFT JOIN (
SELECT * FROM sudoku WHERE x_col = 1 OR y_col = 1
UNION
SELECT * FROM sudoku WHERE x_col BETWEEN 1 AND 3
AND y_col BETWEEN 1 AND 3
) AS forbidden_values ON forbidden_values.val = nums.num
WHERE
forbidden_values.val IS NULL

Making the SQL generic

The SQL above works for cell (1, 1). To make it generic for all x and y values, we need to find out some kind of relationship between x and y and the row, column and block. Here’s all the possible values for any given x and y values.

x or y row column block (x, y)
1 1 1 1, 3
2 2 2 1, 3
3 3 3 1, 3
4 4 4 4, 6
5 5 5 4, 6
6 6 6 4, 6
7 7 7 7, 9
8 8 8 7, 9
9 9 9 7, 9

Looking at the table above, we can see that the forbidden row and column regions are simply the same value as the x or y for the cell. The block region is rather tricky, I think. Here’s the summary:

1. For x or y values 1, 2 and 3, the block’s x or y coordinate is 1
2. For x or y values 4, 5 and 6, the block’s x or y coordinate is 4
3. For x or y values 7, 8 and 9, the block’s x or y coordinate is 7

To map values 1, 2 and 3 to 1, one way to do it is to subtract 1 from the values then integer divide the result then add 1 to it. Thus, we have:

1. (1 – 1) / 3 = 0; 0 + 1 = 1
2. (2 – 1) / 3 = 0; 0 + 1 = 1
3. (3 – 1) / 3 = 0; 0 + 1 = 1

To make the values work for 4, 5, 6 we can add 3 to the result. For 7, 8, 9, we add 6. In other words,

1. For 4, 5, 6, we add 1 * 3 to the result.
2. For 6, 7, 8, we add 2 * 3 to the result.
3. We can even extend this for 1, 2, 3, we add 0 * 3 to the result.

Now that we know to get block x values, getting the block y values should be pretty easy; it is x values + 2. In the formula above, to get y, we can add 3 instead of 1. Well, now that we have a consistent way in getting the result, let’s modify the formula above to a generic form:

For x : ( 3 * ((x – 1) / 3)) + 1
For y : ( 3 * ((x – 1) / 3)) + 3

Final SQL statement for getting legal values

Now that we know how to make it generic, let’s plug it in for the SQL statement we have in the beginning of this page. Assume x and y on the SQL below is a variable.

SELECT nums.* FROM
nums
LEFT JOIN (
SELECT * FROM sudoku WHERE x_col = 1 OR y_col = 1
UNION
SELECT * FROM sudoku WHERE x_col BETWEEN (3 * FLOOR((x  - 1)/ 3)) + 1 AND (3 * FLOOR((x  - 1)/ 3)) + 3
AND y_col BETWEEN (3 * FLOOR((y  - 1)/ 3)) + 1 AND (3 * FLOOR((y  - 1)/ 3)) + 3
) AS forbidden_values ON forbidden_values.val = nums.num
WHERE
forbidden_values.val IS NULL

Now that we know how to get legal values for the cell, let’s turn to the next page for algorithm for solving sudoku.

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.