Brute force sudoku solver algorithm
I’ll be using brute force method in solving the sudoku. The algorithm is outlined as below:
- Loop through all the cell starting at cell (1, 1)
- Check the value of current cell
- If it’s not empty, Go on to the next cell
- If it’s empty, find the first legal value for it
- If it can’t find any legal values, that means that the previous cell may have been assigned the wrong value.
- Track back to the previous cell that was assigned value at step 5. Delete the value.
- 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.
- Here is our initial sudoku puzzle.
- We start from cell (1, 1) then continue to (1, 2) until we reach cell (9, 9) as indicated by the green arrow.
- For cell (1, 1) the legal values are 2, 6, 8. Assign the first possible value 2 to cell (1, 1)
- We go on to the next cell (1, 2). Currently, the only possible value is 6.
- 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).
- 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).
- 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.
- We go on to the next cell (1, 2). Currently, the only possible value is 2.
- We go on to the next cell (1, 5). Once again, we could not find any legal values. So we track back.
- 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.
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].
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
.
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.
@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.