Sudoku solver

Snippets

Insertion_Sort

Works with PostgreSQL

9.0+

Written in

SQL

Depends on

Nothing

Not so fast sudoku solver by me. The input format is: '_' for empty cells, while 'b' to 'j' means 1..9. The board is saved in column-major order, meaning the first column is encoded from top to bottom in the first 9 chars of the string, the following 9 chars are the second column, and so on.

TIP: You can create new sudokus saving a game with ksudoku.

with recursive board(b, p) as (
  -- sudoku board expressed in column-major order, so substr() can be used to fetch a column
  values ('__g_cd__bf_____j____c__e___c__i___jd__b__h___id____e__g__b__f_e_f____g____j_h__c_'::char(81), 0)
  union all select b, p from (
    -- generate boards:
    select overlay(b placing new_char from strpos(b, '_') for 1)::char(81), strpos(b, '_'), new_char
    from board, (select chr(n+ascii('b')) from generate_series(0, 8) n) new_char_table(new_char)
    where strpos(b, '_') > 0
  ) r(b, p, new_char) where
    -- make sure the new_char doesn't appear twice in its column
    -- (there are two checks because we are excluding p itself):
    strpos(substr(b, 1+(p-1)/9*9, (p-1)%9), new_char) = 0 and
    strpos(substr(b, p+1, 8-(p-1)%9), new_char) = 0 and
    -- make sure the new_char doesn't appear twice in its row:
    new_char not in (select substr(b, 1+i*9+(p-1)%9, 1)
                     from generate_series(0, 8) i
                     where p <> 1+i*9+(p-1)%9) and
    -- make sure the new_char doesn't appear twice in its 3x3 block:
    new_char not in (select substr(b, 1+i%3+i/3*9+(p-1)/27*27+(p-1)%9/3*3, 1)
                     from generate_series(0, 8) i
                     where p <> 1+i%3+i/3*9+(p-1)/27*27+(p-1)%9/3*3)
) select
    -- the following subquery is used to represent the board in a '\n' separated human-readable form:
    ( select string_agg((
        select string_agg(chr(ascii('1')+ascii(substr(b, 1+y+x*9, 1))-ascii('b')), '') r
        from generate_series(0, 8) x), E'\n')
      from generate_series(0, 8) y
    ) human_readable,
    b board,
    p depth,
    (select count(*) from board) steps
  from board where strpos(b,'_') = 0 limit 5000;

This example shows how to generically code any backtracking algorithm using Recursive CTE with the following steps:

• Place the initial case before the union of the recursive CTE.
• After the UNION place a query generating the next possible candidate values. In this query you'll be reading the Recursive CTE; make sure you only read incomplete candidates by specifying such condition in a where of that query.
• You may (and probably should) prune invalid candidates if you surround the subquery generating candidate values in another subquery, filtering it with the pruning condition. Pruning is important, not only for speed but because PostgreSQL stores every row this query returns (all the candidate solutions) until it's not needed anymore, and you may run out of disk space (although you can limit that space in PostgreSQL 9.2+ with temp_file_limit, or use a separate temp tablespace otherwise).
• Finally, in the outmost you'll have all the candidates available in the Recursive CTE table. As in this case, if you pruned all the invalid candidates, then all the complete candidates will also be the valid solutions.

The space of possible states will be processed in BFS (breadth-first search).