Don't say postgresql is slower : - I remember now I did then implement the "norvig postgresql", - and it manages a 20% win over your solution with today postgresql 9.3.2.3.
Anyway, it's indeed a "less inefficient" run for now between SQL motors. It remains to be seen if improving SQLite in sudoku solving will improve it for other existing (or not yet imagined) workloads. ** the "norvig" PostgresSQL code ** -- implementing several "logical" algorithms in SQL to solve a sudoku -- -- Norvig algorithm from Peter Norvig, http://norvig.com/sudoku.html -- -- Brut Force algorithm from Anton Scheffer, http://technology.amis.nl/2009/10/13/oracle-rdbms-11gr2-solving-a-sudoku-using-recursive-subquery-factoring/ -- translated per Marcin Mank, http://archives.postgresql.org/pgsql-general/2009-11/msg00150.php -- -- Norvig Algorithm = -- . from given Sudoku problem, generate an array with each cell of the sudoku being a string with all remaining possibilites -- . define as "neighbors" of a cell, all cells which must not have the same piece as this cells, (there are 20 neighbors to each cell) -- . then analyse the cell (the string) have the less remaining solutions, but more than 1, -- .. for a given sudoku position, "play" only on the first cell you found with the less possibilities, and try each of them, -- ... replace in this cell the string by the possible piece you want to try, -- ... remove the piece you played from the neighbors cells own possibilities (as it's no more a possibility for them) -- ... when removing a possibility to a neighbor, if it leave him only on possibility, "play" it immediately, -- ... if you remove all the solutions from a neighbor, than you're not on the sudoku solution path, stop this track. -- -- Brut force Algorithm = -- . try all possible piece in all empty position of the sudoku problem, from top left to bottom right of the sudoku board cells, -- . stop a track each time you can't fill the next position -- -- Speed result : -- . brute force loose on the easy and complex sudo, wins on the medium -- . "Brut" and "Norvig" algorithms seem to stay mono-thread, giving-up the competitive advantage of SQL -- ====================================================================== -- Array usage in SQL ( http://www.postgresql.org/docs/9.2/static/functions-array.html) -- array length (on a dimension) :array_length(anyarray, dimension_integer) -- array to rowset : select unnest(ARRAY[1,2]) -- rowset to array : ARRAY(SELECT * FROM test) -- array to string : select array_to_string(ARRAY[1, 2, 3, NULL, 5], ',', '*') -- string to array : select string_to_array('xx~^~yy~^~zz', '~^~', 'yy') CREATE OR REPLACE function format_string_sudoku(board text []) -- displays a sudoku "board" in 9x9 form with delimiters (so 13 line records) RETURNS setof text LANGUAGE SQL AS $$ with recursive formatted_string(ss , ind ) as (select '' , 81 FROM generate_series(1,1) lp union all select (case when length($1[ind])=1 then $1[ind] else '_' end) || (case when ind % 81=0 then '|<CRLF>=============' when ind % 27=0 then '|<CRLF>|-----------|<CRLF>|' when ind % 9=0 then '|<CRLF>|' when ind % 3=0 then '|' else '' end) || ss , ind-1 from formatted_string where ind>0 ) select unnest(string_to_array( '=============<CRLF>|' || ss, '<CRLF>')) from formatted_string where ind=0 $$; CREATE OR REPLACE function neighbors(cell integer) -- gives back the rowset of neighbors of the given "cell" of any sudoku board RETURNS SETOF integer LANGUAGE SQL AS $$ with list_of(neighbors) as (select unnest(ARRAY[ mod( $1 - 1, 9 ) - 8 + lp * 9 , ( ($1 - 1 ) / 9 ) * 9 + lp , mod( ( ( $1 - 1 ) / 3 ), 3 ) * 3 + ( ( $1 - 1 ) / 27 ) * 27 + lp + ( ( lp - 1 ) / 3 ) * 6]) FROM generate_series(1,9) lp ) select distinct * from list_of where neighbors<>$1 $$; CREATE OR REPLACE function truly_possibles(board text, cell integer) -- gives the table of possible pieces to put in given "cell" of the current sudoku "board" -- including the one already in place, if it exists RETURNS SETOF text LANGUAGE SQL AS $$ select z from (SELECT gs::text AS z FROM generate_series(1,9) gs) z WHERE substr( $1, $2 ,1)=' ' and NOT EXISTS ( SELECT NULL FROM neighbors($2) lp WHERE z = substr( $1, lp , 1 ) ) union select substr( $1, $2 ,1 ) z where substr( $1, $2 ,1 )<>' ' $$; create or replace function create_sudoku_board(initial text) returns setof text[] -- create a sudoku board from the given "s" (string form) sudoku problem language sql as $$ with recursive -- handle several string presentations of the sudoku board problem to solve cleaned_starter(starter) as (select regexp_replace(regexp_replace(initial,'\n|\=|\-|\|', '' ,'g' ),'\.',' ','g' )), -- recursively generate the board from the bottom right cell to the top left of the sudoku board board_generator( t , board , next_cell ) AS ( SELECT starter, array[array_to_string(array(select * from truly_possibles(starter , length(starter) )),'')] , length(starter)-1 from cleaned_starter UNION ALL SELECT t , array[array_to_string(array(select * from truly_possibles(t , next_cell)),'')] ||board, next_cell-1 FROM board_generator where next_cell>0 ) select board from board_generator where next_cell=0 $$; create or replace function next_move(board text []) returns integer -- select a position of the given board with the less solutions (but more than 1) language sql as $$ with recursive -- scan recursively all cells to find the best_cell with the least solutions (over 1) -- don't continue the scanning if you find an ideal "2 solutions" cell before the end board_scanning( best_cell , best_count , this_cell ) AS ( SELECT 0, 99 , array_length(board,1) UNION ALL SELECT (case when this_length between 2 and best_count-1 then this_cell else best_cell end), (case when this_length between 2 and best_count-1 then length(board[this_cell]) else best_count end), (case when this_length=2 then 0 else this_cell-1 end) from (select length(board[this_cell]) this_length , board_scanning.* FROM board_scanning where this_cell>0 ) temp ) select best_cell from board_scanning where this_cell=0 $$; create or replace function play_move(board text [] , best_cell integer, piece text) returns setof text[] -- on the current sudoku "board", play in "best_cell" the given "piece" language sql as $$ -- put the piece in the given best_cell -- then remove that piece from all neighbors possibilities -- if it was the last freedom of a given neighbor, then recursively play the "no_freedom" piece on that neighbor with recursive board_updating( s , neighbor_index , neighborhood ) AS ( -- put the piece in the given best_cell, and prepare to scan the 20 neighbors SELECT board[1:(best_cell-1)] ||array[piece] ||board[(best_cell+1):999], 20 as neighbor_index , array(select * from neighbors(best_cell) as erer) UNION ALL SELECT (case when neighbor_new_freedom=1 and neighbor_old_freedom=2 then -- if it was the last freedom of a given neighbor, then recursively play the "no_freedom" piece on that neighbor play_move(s_after, neighborhood[neighbor_index], s_after[neighborhood[neighbor_index]]) else -- if it not the last freedom of a given neighbor, just proceed on next neighbor s_after end), neighbor_index-1 , neighborhood from ( -- remove the played piece from all neighbors possibilities select s[1:(neighborhood[neighbor_index]-1)] ||replace(s[neighborhood[neighbor_index]], $3, '') ||s[(neighborhood[neighbor_index]+1):999] as s_after, length(replace(s[neighborhood[neighbor_index]], $3, '')) as neighbor_new_freedom, length(s[neighborhood[neighbor_index]]) as neighbor_old_freedom, neighborhood, neighbor_index FROM board_updating where neighbor_index>0 ) as q2 where neighbor_new_freedom > 0 ) -- play induced moves select s from board_updating where neighbor_index=0 -- and s not empty ? $$; --------------------------------- create or replace function solve_a_sudoku_with_brutforce(initial text) returns setof text -- our problem to solve language sql as $$ with recursive -- handle several string presentations of the sudoku board problem to solve cleaned_starter(starter) as (select regexp_replace(regexp_replace(initial,'\n|\=|\-|\|', '' ,'g' ),'\.',' ','g' )), x( s, ind ) as ( select starter, position( ' ' in starter ) from cleaned_starter union all select substr( s, 1, ind - 1 ) || z || substr( s, ind + 1 ) , position(' ' in repeat('x',ind) || substr( s, ind + 1 ) ) from x , (select gs::text as z from generate_series(1,9) gs)z where ind > 0 and not exists ( select null from generate_series(1,9) lp where z.z = substr( s, ( (ind - 1 ) / 9 ) * 9 + lp, 1 ) or z.z = substr( s, mod( ind - 1, 9 ) - 8 + lp * 9, 1 ) or z.z = substr( s, mod( ( ( ind - 1 ) / 3 ), 3 ) * 3 + ( ( ind - 1 ) / 27 ) * 27 + lp + ( ( lp - 1 ) / 3 ) * 6 , 1 ) ) ) select format_string_sudoku(create_sudoku_board(initial)) union all select format_string_sudoku(create_sudoku_board(s)) from x where ind = 0 $$; ------------------------------------------- --------------------------------- create or replace function solve_a_sudoku_with_brutforce(initial text) returns setof text -- our problem to solve language sql as $$ with recursive -- handle several string presentations of the sudoku board problem to solve cleaned_starter(starter) as (select regexp_replace(regexp_replace(initial,'\n|\=|\-|\|', '' ,'g' ),'\.',' ','g' )), neighb(ind_n, lp20) as (select lp, neighbors(lp) from generate_series(1, 81) lp ), x( s, ind ) as ( select starter, position( ' ' in starter ) from cleaned_starter union all select substr( s, 1, ind - 1 ) || z || substr( s, ind + 1 ) , position(' ' in repeat('x',ind) || substr( s, ind + 1 ) ) from (select gs::text as z from generate_series(1,9) gs)z , (select s , ind from x where ind > 0 ) tt where z not in ( select substr( s, lp20 , 1 ) from neighb where ind_n=ind ) ) select format_string_sudoku(create_sudoku_board(initial)) union all select format_string_sudoku(create_sudoku_board(s)) from x where ind = 0 $$; create or replace function solve_a_sudoku_with_norvig(initial text) returns setof text -- our problem to solve language sql as $$ with recursive q (s, next_move , ind) as ( select tt , next_move(tt) as posit ,0 from (select create_sudoku_board(initial) as tt ) sds union select tt , next_move(tt) as posit , ind+1 from (select play_move(s, next_move, unnest(string_to_array(s[next_move] ,Null)))as tt , ind from q where next_move>0) as ertrt ) select format_string_sudoku(create_sudoku_board(initial)) union all select format_string_sudoku(s) from q where next_move = 0 $$; ------------- create or replace function solve_a_sudoku(initial text, algorithm text) returns setof text language sql as $$ select (case when lower(algorithm)='norvig' then solve_a_sudoku_with_norvig(initial) else solve_a_sudoku_with_brutforce(initial) end) $$; ------------- create or replace function sudoku_problem(initial integer) returns text -- all our problems language sql as $$ select portfolio[initial] from (select array[ ' 53..7.... 6..195... .98....6. 8...6...3 4..8.3..1 7...2...6 .6....28. ...419..5 ....8..79' --easy --"534678912672195348198342567859761423426853791713924856961537284287419635345286179" ,'1....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3..' -- medium --"162857493534129678789643521475312986913586742628794135356478219241935867897261354" ,'8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..' --hardest (35s) --"812753649943682175675491283154237896369845721287169534521974368438526917796318452" ,'1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1' --hard (28s) "easter monster" ] as portfolio) as our_portfolio $$; -- let's play sudoku -- problem ( 1 or 2 or 3) , algorithm choosen ('Norvig' or 'Brutforce') -- beware , response time of up to 5 minutes on problem 3 with 'Brutforce' algorithm --select lp, array(select neighbors(lp) from generate_series(1,1 ) --) from generate_series(1, 81) lp select solve_a_sudoku(sudoku_problem(3), 'Norvig') _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
