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

I have no idea why I would want to solve sudoku in PostgreSQL PL/pgSQL. My guess would be just for the fun of it. I’m also hoping that it can serve as a tutorial example in programming PostgreSQL PL/pgSQL.

So what is sudoku? It is basically a number puzzle where the objective is to fill 9×9 grid so that the columns, rows, and the smaller 3×3 squares, called blocks, doesn’t have the same number repeated. If you’re not familiar with sudoku, this Wikipedia page on sudoku may be helpful.

Now that you’re familiar with sudoku, there are many algorithms for solving sudoku. For this solution, I’ve decided to use brute force algorithm.

If you’re just interested in the end result, please jump to last page.

Table structure for sudoku

The table to represent sudoku is pretty straight forward. It’s basically 4 columns that describe:

  • The x and y coordinate for each sudoku cell
  • The value of the cell
  • A marker to identify whether the value is given. I call this is_permanent
CREATE TABLE sudoku (
	x_col integer NOT NULL,
	y_col integer NOT NULL,
	val integer,
	is_permanent boolean NOT NULL DEFAULT false,
	CONSTRAINT sudoku_pkey PRIMARY KEY (x_col, y_col)
) WITHOUT OIDS;

In addition to sudoku table, I I’ll need to get a list of possible values. So rather than typing it every time in query string, I thought it would be convenient to have a table with a list of legal values.

CREATE TABLE nums (
	num integer NOT NULL DEFAULT 1,
	CONSTRAINT nums_pkey PRIMARY KEY (num)
) WITHOUT OIDS;

INSERT INTO nums VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9);

Test case sudoku puzzle

For the purpose of testing the solution, let’s start with a rather easy to solve by hand. The puzzle and the solution is as below:

sudoku problem
sudoku problem solved

Populating sudoku table

Now that we have the puzzle to solve, let’s insert the known values into our sudoku table.

INSERT INTO sudoku (x_col, y_col, val, is_permanent) VALUES
	('1','3','5', TRUE), ('1','4','1', TRUE), ('1','6','9', TRUE),
	('1','7','4', TRUE), ('1','8','7', TRUE), ('1','9','3', TRUE),
	('2','3','9', TRUE), ('2','4','5', TRUE), ('2','7','8', TRUE),
	('2','9','6', TRUE), ('3','1','1', TRUE), ('3','2','4', TRUE),
	('3','4','8', TRUE), ('3','7','2', TRUE), ('4','1','4', TRUE),
	('4','8','6', TRUE), ('5','3','6', TRUE), ('5','4','7', TRUE),
	('5','6','2', TRUE), ('5','7','5', TRUE), ('6','2','8', TRUE),
	('6','9','1', TRUE), ('7','3','4', TRUE), ('7','6','1', TRUE),
	('7','8','2', TRUE), ('7','9','8', TRUE), ('8','1','5', TRUE),
	('8','3','2', TRUE), ('8','6','8', TRUE), ('8','7','6', TRUE),
	('9','1','3', TRUE), ('9','2','9', TRUE), ('9','3','8', TRUE),
	('9','4','2', TRUE), ('9','6','7', TRUE), ('9','7','1', TRUE)
;

On the next page, we’ll discuss on how to determine valid values for a given cell.

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


2 × = two