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

PostgreSQL sudoku solver function

We’ve discussed the solution for 3 pages. I think we cover everything that I feel needs attention. Without further due, here’s the full function definition for solving sudoku in pure PostgreSQL PL/pgSQL.

CREATE OR REPLACE FUNCTION func_solve_sudoku()
  RETURNS INTEGER AS
$BODY$DECLARE
	query_result RECORD;
	initial_x INTEGER;
	initial_y INTEGER;
	initial_proposed_val INTEGER;
	is_finished BOOLEAN;
BEGIN
	initial_x = 1;
	initial_y = 1;
	initial_proposed_val = 1;

	<< main_loop >>
	LOOP
		<< cell_loop >>
		FOR x IN initial_x .. 9 LOOP
			is_finished = TRUE;
			FOR y IN initial_Y .. 9 LOOP
				-- Check if cell (x, y) has value.
				SELECT INTO query_result * FROM sudoku WHERE x_col = x AND y_col = y;
				IF NOT FOUND THEN
					-- Check all allowable values.
					SELECT INTO query_result nums.* FROM
						nums
						LEFT JOIN (
							SELECT * FROM sudoku WHERE x_col = x OR y_col = y
							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
						AND nums.num >= initial_proposed_val
					LIMIT 1
					;

					IF FOUND THEN
						RAISE NOTICE 'Found % for (%, %)', query_result.num , x, y;
						INSERT INTO sudoku VALUES (x, y, query_result.num, FALSE);
						initial_proposed_val = 1;
					ELSE
						RAISE NOTICE 'No legal values found for (%, %). Tracking back', x, y;

						FOR x1 IN REVERSE x .. 1 LOOP
							FOR y1 IN REVERSE y .. 1 LOOP
								SELECT INTO query_result * FROM sudoku WHERE x_col = x1 AND y_col = y1 AND is_permanent IS FALSE;
								IF FOUND THEN
									initial_x = x1;
									initial_y = y1;
									initial_proposed_val = query_result.val + 1;

									DELETE FROM sudoku WHERE x_col = x1 AND y_col = y1 AND is_permanent IS FALSE;
									is_finished = FALSE;

									RAISE NOTICE '(%, %) is to be reassigned with value other than %', x1, y1, query_result.val;
									IF initial_proposed_val > 9 THEN
										RAISE NOTICE 'Since (%, %) is to be reassigned value other than %, we have no legal value', x1, y1, query_result.val;
									ELSE
										EXIT cell_loop;
									END IF;
								END IF;
							END LOOP;
							y = 9;
						END LOOP;

						EXIT main_loop;
					END IF;

				END IF;
			END LOOP;
			initial_y = 1;
		END LOOP;

		EXIT WHEN is_finished = TRUE;
	END LOOP;

	RAISE NOTICE 'End.';

	SELECT INTO query_result COUNT(*) AS cnt FROM sudoku;

	IF query_result.cnt = 81 THEN
		RETURN 1;
	ELSE
		RETURN 0;
	END IF;
END;$BODY$
  LANGUAGE 'plpgsql' VOLATILE;

One thing that I’d like to point out on the function definition above is the use of RAISE NOTICE function for spitting out debugging information for us to follow the algorithm steps.

Executing sudoku solver function

To solve sudoku, run the following query. Note that the query on line 1 is just to get the puzzle back to its original state.

DELETE FROM sudoku WHERE is_permanent = FALSE;
SELECT func_solve_sudoku();

Possible improvements on trackback section

There’s one improvement that we can do to the PostgreSQL PL/pgSQL function that solves sudoku puzzle above. Although the improvement is very minor for reasons I’ll mention afterwards, I think it’s worthwhile to be mentioned.

LOOP
	SELECT INTO query_result * FROM sudoku WHERE is_permanent IS FALSE ORDER BY ((x_col * 10) + y_col) DESC LIMIT 1;
	IF FOUND THEN
		initial_x = query_result.x_col;
		initial_y = query_result.y_col;
		initial_proposed_val = query_result.val + 1;

		DELETE FROM sudoku WHERE x_col = initial_x AND y_col = initial_y AND is_permanent IS FALSE;
		is_finished = FALSE;
		IF initial_proposed_val <= 9 THEN
			EXIT cell_loop;
		END IF;
	ELSE
		EXIT;
	END IF;
	EXIT WHEN initial_proposed_val <= 9;
END LOOP;
EXIT main_loop;

If you start assigning id to each cells in such a way that as we move forward (see page 3 for how we traverse the puzzle) the id is bigger, finding the last cell to be reversed can be achieved by getting the highest id cell that’s not marked as permanent. Therefore, the improvement eliminates the nested loop FOR xxx IN REVERSE and replaces it with a single SQL call.

So why do I think it’s a minimal improvements? Well, think about it .. there’s a good chance when you track back, the cell won’t be that far away from current cell. Thus, the loop, even though it’s nested, will most likely run a few times. The best case scenario for this improvement is when you’re at cell (9, 9) and for somehow you need to track back all the way to cell (1, 1). If we just need to go back 1 cell, then there really is not much improvements.

There you have it … I hope you enjoyed this article. Please leave comments / suggestions / questions if you have. I’m looking forward to improving my solution with your comments / suggestions / questions.

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.