Sudoku: Difference between revisions

Line 8,154:

=={{header|Phix}}==

Simple brute force solution. Generally quite good but will struggle on some puzzles (eg see "the beast" below)

<lang Phix>~~sequence board = split~~(~~"""~~

with javascript_semantics

.......39

sequence board = split("""

.....1..5

..3.5.8..

.......39

..8.9...6

.....1..5

.7...2...

..3.5.8..

1..4.....

..8.9...6

..9.8..5.

.7...2...

.2....6..

1..4.....

4..7....~~.""",'\n')~~

..9.8..5.

.2....6..

4..7.....""",'\n')

function valid_move(integer y, integer x, integer ch)

for i=1 to 9 do

function valid_move(integer y, x, ch)

if ch=board[i][x] then return 0 end if

for i=1 to 9 do

if ch=board[y][i] then return 0 end if

if ch=board[i][x] then return false end if

end for

if ch=board[y][i] then return false end if

y -= mod(y-1,3)

end for

x -= mod(x-1,3)

y -= mod(y-1,3)

for ys=y to y+2 do

x -= mod(x-1,3)

for xs=x to x+2 do

for ys=y to y+2 do

if ch=board[ys][xs] then return 0 end if

for xs=x to x+2 do

end for

if ch=board[ys][xs] then return false end if

end for

end for

return 1

end for

end function

return true

end function

sequence solution = {}

sequence solution = {}

procedure brute_solve()

for y=1 to 9 do

procedure brute_solve()

for x=1 to 9 do

for y=1 to 9 do

if board[y][x]<='0' then

for x=1 to 9 do

for ch='1' to '9' do

if board[y][x]<='0' then

if valid_move(y,x,ch) then

for ch='1' to '9' do

board[y][x] = ch

if valid_move(y,x,ch) then

brute_solve()

board[y][x] = ch

board[y][x] = ' '

if ~~length(solution)~~ ~~then~~ ~~return~~ ~~end~~ if

brute_solve()

board[y][x] = ' '

end if

if length(solution) then return end if

end for

end if

return

end for

end if

return

end for

end if

end for

end for

solution = board -- (already solved case)

end for

end procedure

solution = deep_copy(board) -- (already solved case)

end procedure

atom t0 = time()

brute_solve()

atom t0 = time()

printf(1,"%s\n(solved in %3.2fs)\n",{join(solution,"\n"),time()-t0})</lang>

brute_solve()

printf(1,"%s\n(solved in %3.2fs)\n",{join(solution,"\n"),time()-t0})

<pre>

Line 8,221:

Line 8,224:

contains 339 puzzles, can be run as a command-line or gui program, check for multiple solutions, and produce

a more readable single-puzzle output (example below).

<lang Phix>-- Working directly on 81-character strings ultimately proves easier: Originally I

with javascript_semantics

-- just wanted to simplify the final display, but later I realised that a 9x9 grid

-- Working directly on 81-character strings ultimately proves easier: Originally I

-- encourages laborious indexing/looping everwhere whereas using a flat 81-element

-- just wanted to simplify the final display, but later I realised that a 9x9 grid

-- approach encourages precomputation of index sets, and once you commit to that,

-- encourages laborious indexing/looping everwhere whereas using a flat 81-element

-- the rest of the code starts to get a whole lot cleaner. Below we create 27+18

-- approach encourages precomputation of index sets, and once you commit to that,

-- sets and 5 tables of lookup indexes to locate them quickly.

-- the rest of the code starts to get a whole lot cleaner. Below we create 27+18

-- sets and 5 tables of lookup indexes to locate them quickly.

sequence nines = {}, -- will be 27 in total

cols = repeat(0,9*9), -- remainder(i-1,9)+1

sequence nines = {}, -- will be 27 in total

rows = repeat(0,9*9), -- floor((i-1)/9)+10

cols = repeat(0,9*9), -- remainder(i-1,9)+1

squares = repeat(0,9*9),

rows = repeat(0,9*9), -- floor((i-1)/9)+10

sixes = {}, -- will be 18 in total

squares = repeat(0,9*9),

dotcol = repeat(0,9*9), -- same col, diff square

sixes = {}, -- will be 18 in total

dotrow = repeat(0,9*9) -- same row, diff square

dotcol = repeat(0,9*9), -- same col, diff square

dotrow = repeat(0,9*9) -- same row, diff square

procedure set_nines()

sequence nine, six

procedure set_nines()

integer idx, ndx

sequence nine, six

for x=0 to 8 do -- columns

integer idx, ndx

nine = {}

for x=0 to 8 do -- columns

ndx = length(nines)+1

nine = {}

for y=1 to 81 by 9 do

ndx = length(nines)+1

idx = y+x

for y=1 to 81 by 9 do

nine = append(nine,idx)

idx = y+x

cols[idx] = ndx

nine = append(nine,idx)

end for

cols[idx] = ndx

nines = append(nines,nine)

end for

end for

nines = append(nines,nine)

for y=1 to 81 by 9 do -- rows

end for

nine = {}

for y=1 to 81 by 9 do -- rows

ndx = length(nines)+1

nine = {}

for x=0 to 8 do

ndx = length(nines)+1

idx = y+x

for x=0 to 8 do

nine = append(nine,idx)

idx = y+x

rows[idx] = ndx

nine = append(nine,idx)

end for

rows[idx] = ndx

nines = append(nines,nine)

end for

end for

nines = append(nines,nine)

if length(nines)!=18 then ?9/0 end if

end for

for y=0 to 8 by 3 do -- small squares [19..27]

if length(nines)!=18 then ?9/0 end if

for x=0 to 8 by 3 do

for y=0 to 8 by 3 do -- small squares [19..27]

nine = {}

for x=0 to 8 by 3 do

ndx = length(nines)+1

nine = {}

for sy=y*9 to y*9+18 by 9 do

ndx = length(nines)+1

for sx=x to x+2 do

for sy=y*9 to y*9+18 by 9 do

idx = sy+sx+1

for sx=x to x+2 do

nine = append(nine,idx)

idx = sy+sx+1

squares[idx] = ndx

nine = append(nine,idx)

end for

squares[idx] = ndx

end for

end for

nines = append(nines,nine)

end for

end for

nines = append(nines,nine)

end for

end for

if length(nines)!=27 then ?9/0 end if

end for

for i=1 to 9*9 do

if length(nines)!=27 then ?9/0 end if

six = {}

for i=1 to 9*9 do

nine = nines[cols[i]] -- dotcol

six = {}

for j=1 to length(nine) do

nine = nines[cols[i]] -- dotcol

if squares[i]!=squares[nine[j]] then

for j=1 to length(nine) do

six = append(six,nine[j])

if squares[i]!=squares[nine[j]] then

end if

six = append(six,nine[j])

end for

end if

ndx = find(six,sixes)

end for

if ndx=0 then

ndx = find(six,sixes)

sixes = append(sixes,six)

if ndx=0 then

ndx = length(sixes)

sixes = append(sixes,six)

end if

ndx = length(sixes)

dotcol[i] = ndx

end if

six = {}

dotcol[i] = ndx

nine = nines[rows[i]] -- dotrow

six = {}

for j=1 to length(nine) do

nine = nines[rows[i]] -- dotrow

if squares[i]!=squares[nine[j]] then

for j=1 to length(nine) do

six = append(six,nine[j])

if squares[i]!=squares[nine[j]] then

end if

six = append(six,nine[j])

end for

end if

ndx = find(six,sixes)

end for

if ndx=0 then

ndx = find(six,sixes)

sixes = append(sixes,six)

if ndx=0 then

ndx = length(sixes)

sixes = append(sixes,six)

end if

ndx = length(sixes)

dotrow[i] = ndx

end if

end for

dotrow[i] = ndx

end procedure

end for

set_nines()

end procedure

set_nines()

integer improved = 0

integer improved = 0

function eliminate_in(sequence valid, sequence set, integer ch)

for i=1 to length(set) do

function eliminate_in(sequence valid, set, integer ch)

integer idx = set[i]

for i=1 to length(set) do

if string(valid[idx]) then

integer idx = set[i]

integer k = find(ch,valid[idx])

if string(valid[idx]) then

if k!=0 then

integer k = find(ch,valid[idx])

valid[idx][k..k] = ""

if k!=0 then

improved = 1

valid[idx][k..k] = ""

end if

improved = 1

end if

end if

end for

end if

return valid

end for

end function

return valid

end function

function test_comb(sequence chosen, sequence pool, sequence valid)

--

function test_comb(sequence chosen, pool, valid)

-- (see deep_logic()/set elimination)

--

-- chosen is a sequence of length 2..4 of integers 1..9: ordered elements of pool.

-- (see deep_logic()/set elimination)

-- pool is a set of elements of the sequence valid, each of which is a sequence.

-- chosen is a sequence of length 2..4 of integers 1..9: ordered elements of pool.

-- (note that elements of valid in pool not in chosen are not necessarily sequences)

-- pool is a set of elements of the sequence valid, each of which is a sequence.

--

-- (note that elements of valid in pool not in chosen are not necessarily sequences)

sequence contains = repeat(0,9)

--

integer ccount = 0, ch

sequence contains = repeat(0,9)

object set

integer ccount = 0, ch

object set

for i=1 to length(chosen) do

set = valid[pool[chosen[i]]]

for i=1 to length(chosen) do

for j=1 to length(set) do

set = valid[pool[chosen[i]]]

ch = set[j]-'0'

for j=1 to length(set) do

if contains[ch]=0 then

ch = set[j]-'0'

contains[ch] = 1

if contains[ch]=0 then

ccount += 1

contains[ch] = 1

end if

ccount += 1

end for

end if

end for

end for

if ccount=length(chosen) then

end for

for i=1 to length(pool) do

if ccount=length(chosen) then

if find(i,chosen)=0 then

valid = deep_copy(valid)

set = valid[pool[i]]

for i=1 to length(pool) do

if sequence(set) then

if find(i,chosen)=0 then

-- (reverse order so deletions don't foul indexes)

set = valid[pool[i]]

for j=length(set) to 1 by -1 do

if sequence(set) then

ch = set[j]-'0'

-- (reverse order so deletions don't foul indexes)

if contains[ch] then

for j=length(set) to 1 by -1 do

valid[pool[i]][j..j] = ""

ch = set[j]-'0'

improved = 1

if contains[ch] then

end if

valid[pool[i]][j..j] = ""

end for

improved = 1

end if

end if

end if

end for

end for

end if

end if

end if

return valid

end for

end function

end if

return valid

-- from [[Combinations#Phix|Combinations]]

end function

-- from http://rosettacode.org/wiki/Combinations#Phix

function comb(sequence pool, valid, integer needed, done=0, sequence chosen={})

-- from [[Combinations#Phix|Combinations]]

-- (used by deep_logic()/set elimination)

-- from http://rosettacode.org/wiki/Combinations#Phix

if needed=0 then -- got a full set

function comb(sequence pool, valid, integer needed, done=0, sequence chosen={})

return test_comb(chosen,pool,valid)

-- (used by deep_logic()/set elimination)

end if

if needed=0 then -- got a full set

if done+needed>length(pool) then return valid end if -- cannot fulfil

return test_comb(chosen,pool,valid)

-- get all combinations with and without the next item:

end if

done += 1

if done+needed>length(pool) then return valid end if -- cannot fulfil

if sequence(valid[pool[done]]) then

-- get all combinations with and without the next item:

valid = comb(pool,valid,needed-1,done,append(chosen,done))

done += 1

end if

if sequence(valid[pool[done]]) then

return comb(pool,valid,needed,done,chosen)

valid = comb(pool,valid,needed-1,done,append(deep_copy(chosen),done))

end function

end if

return comb(pool,valid,needed,done,chosen)

function deep_logic(string board, sequence valid)

end function

--

-- Create a grid of valid moves. Note this does not modify board, but instead creates

function deep_logic(string board, sequence valid)

-- sets of permitted values for each cell, which can also be and are used for hints.

--

-- Apply standard eliminations of known cells, then try some more advanced tactics:

-- Create a grid of valid moves. Note this does not modify board, but instead creates

--

-- sets of permitted values for each cell, which can also be and are used for hints.

-- 1) row/col elimination

-- Apply standard eliminations of known cells, then try some more advanced tactics:

-- If in any of the 9 small squares a number can only occur in one row or column,

--

-- then that number cannot occur in that row or column in two other corresponding

-- 1) row/col elimination

-- small squares. Example (this one with significant practical benefit):

-- If in any of the 9 small squares a number can only occur in one row or column,

-- 000|000|036

-- then that number cannot occur in that row or column in two other corresponding

-- 840|000|000

-- small squares. Example (this one with significant practical benefit):

-- 000|000|020

-- ~~---+---+---~~

-- 000|000|036

-- ~~000~~|~~203~~|000

-- 840|000|000

-- ~~010~~|000|~~700~~

-- 000|000|020

-- ~~000|600|400~~

-- ---+---+---

-- ~~---+---+---~~

-- 000|203|000

-- ~~000~~|~~410~~|~~050~~

-- 010|000|700

-- ~~003|~~000|~~200~~

-- 000|600|400

-- ~~600|000|000 <~~-- 3

-- ---+---+---

-- ~~^-- 3~~

-- 000|410|050

-- 003|000|200

-- Naively, the br can contain a 3 in the four corners, but looking at mid-right and

-- 600|000|000 <-- 3

-- mid-bottom leads us to eliminating 3s in column 9 and row 9, leaving 7,7 as the

-- ~~only~~ ~~square~~ in ~~the~~ br ~~that~~ ~~can~~ be a 3. ~~Uses~~ ~~dotcol~~ ~~and~~ ~~dotrow.~~

-- ^-- 3

-- ~~Without this~~, ~~brute~~ ~~force~~ on ~~the~~ ~~above~~ ~~takes~~ ~~~8s~~, but ~~with~~ it ~~~0s~~

-- Naively, the br can contain a 3 in the four corners, but looking at mid-right and

-- mid-bottom leads us to eliminating 3s in column 9 and row 9, leaving 7,7 as the

--

-- only square in the br that can be a 3. Uses dotcol and dotrow.

-- 2) set elimination

-- Without this, brute force on the above takes ~8s, but with it ~0s

-- If in any 9-set there is a set of n blank squares that can only contain n digits,

--

-- then no other squares can contain those digits. Example (with some benefit):

-- 2) set elimination

-- 75.|.9.|.46

-- If in any 9-set there is a set of n blank squares that can only contain n digits,

-- 961|...|352

-- then no other squares can contain those digits. Example (with some benefit):

-- 4..|...|79.

-- ~~---+---+---~~

-- 75.|.9.|.46

-- 2..|6.1|~~..7~~

-- 961|...|352

-- .8.|...|.2.

-- 4..|...|79.

-- ~~1..|328|.65~~

-- ---+---+---

-- ~~---+---+---~~

-- 2..|6.1|..7

-- ...|...|..~~. <-- [7,8] is {1,3,8}, [7,9] is {1,3,8}~~

-- .8.|...|.2.

-- ~~3.9|.~~..|2.~~4 <-- [8,8] is {1,8}~~

-- 1..|328|.65

-- ~~84.|.3.|.79~~

-- ---+---+---

-- ~~The~~ ~~three~~ ~~cells~~ ~~above~~ ~~the~~ br ~~479~~ ~~can~~ ~~only~~ ~~contain~~ {1,3,8}, so ~~the .. of the .2.~~

-- ...|...|... <-- [7,8] is {1,3,8}, [7,9] is {1,3,8}

-- in ~~column~~ 7 of ~~that~~ ~~square~~ ~~are~~ ~~{5,6}~~ ~~(not~~ 1) ~~and~~ ~~hence~~ [9,4] ~~must be a~~ 1.

-- 3.9|...|2.4 <-- [8,8] is {1,8}

-- 84.|.3.|.79

-- (Relies on plain_logic to spot that "must be a 1", and serves as a clear example

-- of ~~why~~ ~~this~~ ~~routine~~ ~~should~~ ~~not~~ ~~bother~~ to ~~attempt~~ ~~updating~~ the ~~board~~ ~~itself~~ - as

-- The three cells above the br 479 can only contain {1,3,8}, so the .. of the .2.

-- it ~~spends~~ ~~almost~~ ~~all~~ of ~~its~~ ~~time~~ ~~looking~~ in a ~~completely~~ ~~different~~ ~~place~~.)

-- in column 7 of that square are {5,6} (not 1) and hence [9,4] must be a 1.

-- (~~One~~ ~~could~~ ~~argue~~ that ~~[7,7]~~ ~~and~~ [9,7] ~~are~~ ~~the~~ ~~only~~ ~~places~~ ~~that~~ ~~can~~ ~~hold {5,6} and~~

-- (Relies on plain_logic to spot that "must be a 1", and serves as a clear example

-- ~~therefore~~ we should ~~eliminate~~ ~~all~~ ~~non-{5,6}~~ ~~from~~ ~~those~~ ~~squares,~~ as an ~~alternative~~

-- of why this routine should not bother to attempt updating the board itself - as

-- it spends almost all of its time looking in a completely different place.)

-- strategy. However I think that would be harder to code and cannot imagine a case

-- ~~said~~ ~~complementary~~ ~~logic~~ ~~covers~~, ~~that~~ the ~~above~~ ~~does~~ ~~not~~, ~~cmiiw.)~~

-- (One could argue that [7,7] and [9,7] are the only places that can hold {5,6} and

-- therefore we should eliminate all non-{5,6} from those squares, as an alternative

--

-- strategy. However I think that would be harder to code and cannot imagine a case

-- 3) x-wings

-- said complementary logic covers, that the above does not, cmiiw.)

-- If a pair of rows or columns can only contain a given number in two matching places,

--

-- then once filled they will occupy opposite diagonal corners, hence that said number

-- 3) x-wings

-- cannot occur elsewhere in those two columns/rows. Example (with a benefit):

-- ~~.43|98.|25.~~ ~~<--~~ 6 in ~~[1,{6~~,~~9}]~~

-- If a pair of rows or columns can only contain a given number in two matching places,

-- then once filled they will occupy opposite diagonal corners, hence that said number

-- 6..|425|...

-- cannot occur elsewhere in those two columns/rows. Example (with a benefit):

-- 2..|..1|.94

-- --~~-+---+---~~

-- .43|98.|25. <-- 6 in [1,{6,9}]

-- 9..|..4|.~~7. <-- hence 6 not in [4,9]~~

-- 6..|425|...

-- 3..|6.8|...

-- 2..|..1|.94

-- ~~41.|2.9|..3~~

-- ---+---+---

-- --~~-+---+---~~

-- 9..|..4|.7. <-- hence 6 not in [4,9]

-- 82.|5..|... ~~<-- hence 6 not in [7,6],[7,9]~~

-- 3..|6.8|...

-- ...|.4.|..~~5 <-- hence 6 not in [8,6]~~

-- 41.|2.9|..3

-- ~~534|89.|71. <~~-- ~~6 in [9,{6,9}]~~

-- ---+---+---

-- A 6 ~~must~~ be in ~~[1,6]~~ or ~~[1,9]~~ ~~and~~ ~~[9,6]~~ or ~~[9,9],~~ ~~hence~~ ~~[7,9]~~ is ~~not~~ 6 ~~and~~ ~~must~~ be 9.

-- 82.|5..|... <-- hence 6 not in [7,6],[7,9]

-- ...|.4.|..5 <-- hence 6 not in [8,6]

-- (we also eliminate 6 from [4,9], [7,6] and [8,6] to no great use)

-- In ~~practice~~ ~~this~~ ~~offers~~ ~~little~~ ~~benefit~~ ~~over~~ a ~~single~~ ~~trial~~-~~and~~-~~error~~ ~~step,~~ as

-- 534|89.|71. <-- 6 in [9,{6,9}]

-- ~~obviously~~ ~~trying~~ ~~either 6~~ in ~~row~~ 1 or 9 ~~immediately~~ ~~pinpoints~~ ~~that~~ 9 ~~anyway~~.

-- A 6 must be in [1,6] or [1,9] and [9,6] or [9,9], hence [7,9] is not 6 and must be 9.

-- (we also eliminate 6 from [4,9], [7,6] and [8,6] to no great use)

--

-- In practice this offers little benefit over a single trial-and-error step, as

-- 4) swordfish (not attempted)

-- obviously trying either 6 in row 1 or 9 immediately pinpoints that 9 anyway.

-- There is an extension to x-wings known as swordfish: three (or more) pairs form

--

-- a staggered pair (or more) of rectangles that exhibit similar properties, eg:

-- 4) swordfish (not attempted)

-- 8-1|-5-|-3-

-- There is an extension to x-wings known as swordfish: three (or more) pairs form

-- 953|-68|---

-- a staggered pair (or more) of rectangles that exhibit similar properties, eg:

-- -4-|-*3|5*8

-- ---~~+---+-~~--

-- 8-1|-5-|-3-

-- ~~6--~~|9-2|---

-- 953|-68|---

-- -8-|-3-|~~-4-~~

-- -4-|-*3|5*8

-- 3*-|5-1|-*7 <-- ~~hence [6,3] is not 9, must be 4~~

-- ---+---+---

-- ---~~+---+~~---

-- 6--|9-2|---

-- ~~5*2~~|-*-|-8-

-- -8-|-3-|-4-

-- --8|37-|--9

-- 3*-|5-1|-*7 <-- hence [6,3] is not 9, must be 4

-- -3-~~|82~~-|1--

-- ---+---+---

-- ^---^-~~--^-- 3 pairs of 9s (marked with *) on 3 rows (only)~~

-- 5*2|-*-|-8-

-- --8|37-|--9

-- It is not a swordfish if the 3 pairs are on >3 rows, I trust that is obvious.

-- -3-|82-|1--

-- Logically you can extend this to N pairs on N rows, however I cannot imagine a

-- ^---^---^-- 3 pairs of 9s (marked with *) on 3 rows (only)

-- case where this is not immediately solved by a single trial-step being invalid.

-- ~~(eg~~ ~~above~~ if ~~you~~ ~~try~~ ~~[3,5]:=9~~ it is ~~quickly~~ ~~proved~~ to be ~~invalid~~, ~~and~~ ~~the~~ ~~same~~

-- It is not a swordfish if the 3 pairs are on >3 rows, I trust that is obvious.

-- Logically you can extend this to N pairs on N rows, however I cannot imagine a

-- goes for [6,8]:=9 and [7,2]:=9, since they are all entirely inter-dependent.)

-- ~~Obviously~~ where I ~~have~~ ~~said~~ ~~rows,~~ ~~the~~ ~~same~~ ~~concept~~ ~~can~~ ~~be applied~~ to ~~columns~~.

-- case where this is not immediately solved by a single trial-step being invalid.

-- (eg above if you try [3,5]:=9 it is quickly proved to be invalid, and the same

-- Likewise there are "Alternate Pairs" and "Hook or X-Y wing" strategies, which

-- goes for [6,8]:=9 and [7,2]:=9, since they are all entirely inter-dependent.)

-- are easily solved with a single trial-and-error step, and of course the brute

-- ~~force~~ ~~algorithm~~ is ~~going~~ to ~~select~~ ~~pairs~~ ~~first~~ ~~anyway.~~ ~~[Erm,~~ no it ~~doesn't,~~

-- Obviously where I have said rows, the same concept can be applied to columns.

-- Likewise there are "Alternate Pairs" and "Hook or X-Y wing" strategies, which

-- it selects shortest - I've noted the possible improvement below.]

-- are easily solved with a single trial-and-error step, and of course the brute

--

-- force algorithm is going to select pairs first anyway. [Erm, no it doesn't,

integer col, row

-- it selects shortest - I've noted the possible improvement below.]

sequence c, r

--

sequence nine, prevsets, set

integer k -- (scratch)

object vj

if length(valid)=0 then

integer ch, k, idx, sx, sy, count

-- initialise/start again from scratch

valid = repeat("123456789",9*9)

if length(valid)=0 then

end if

-- initialise/start again from scratch

--

valid = repeat("123456789",9*9)

-- First perform standard eliminations of any known cells:

end if

-- (repeated every time so plain_logic() does not have to worry about it)

--

--

-- First perform standard eliminations of any known cells:

for i=1 to 9*9 do

-- (repeated every time so plain_logic() does not have to worry about it)

integer ch = board[i]

--

if ch>'0'

for i=1 to 9*9 do

and string(valid[i]) then

ch = board[i]

valid[i] = ch

if ch>'0'

valid = eliminate_in(valid,nines[cols[i]],ch)

and string(valid[i]) then

valid = eliminate_in(valid,nines[rows[i]],ch)

valid[i] = ch

valid = eliminate_in(valid,nines[squares[i]],ch)

valid = eliminate_in(valid,nines[cols[i]],ch)

end if

valid = eliminate_in(valid,nines[rows[i]],ch)

end for

valid = eliminate_in(valid,nines[squares[i]],ch)

--

end if

-- 1) row/col elimination

end for

--

--

for s=19 to 27 do

-- 1) row/col elimination

sequence c = repeat(0,9), -- 0 = none seen, 1..9 this col only, -1: >1 col

--

r = repeat(0,9), -- "" row row

for s=19 to 27 do

nine = nines[s]

c = repeat(0,9) -- 0 = none seen, 1..9 this col only, -1: >1 col

integer row, col, ch

r = repeat(0,9) -- "" row row

for n=1 to 9 do

nine = nines[s]

k = nine[n]

for n=1 to 9 do

object vk = valid[k]

k = nine[n]

if string(vk) then

vj = valid[k]

for i=1 to length(vk) do

if string(vj) then

ch = vk[i]-'0'

for i=1 to length(vj) do

col = dotcol[k]

ch = vj[i]-'0'

row = dotrow[k]

col = dotcol[k]

c[ch] = iff(find(c[ch],{0,col})!=0?col:-1)

row = dotrow[k]

r[ch] = iff(find(r[ch],{0,row})!=0?row:-1)

c[ch] = iff(find(c[ch],{0,col})!=0?col:-1)

end for

r[ch] = iff(find(r[ch],{0,row})!=0?row:-1)

end ~~for~~

end if

end for

end if

for i=1 to 9 do

end for

ch = i+'0'

for i=1 to 9 do

col = c[i]

ch = i+'0'

if col>0 then

col = c[i]

valid = eliminate_in(valid,sixes[col],ch)

if col>0 then

end if

valid = eliminate_in(valid,sixes[col],ch)

row = r[i]

end if

if row>0 then

row = r[i]

valid = eliminate_in(valid,sixes[row],ch)

if row>0 then

end if

valid = eliminate_in(valid,sixes[row],ch)

end for

end if

end for

end for

--

end for

--

-- 2) set elimination

-- ~~2) set elimination~~

--

for i=1 to length(nines) do

--

--

for i=1 to length(nines) do

-- Practical note: Meticulously counting empties to eliminate larger set sizes

--

-- would at best reduce 6642 tests to 972, not deemed worth it.

-- Practical note: Meticulously counting empties to eliminate larger set sizes

--

-- would at best reduce 6642 tests to 972, not deemed worth it.

for set_size=2 to 4 do

--

--if floor(count_empties(nines[i])/2)>=set_size then -- (untested)

for set_size=2 to 4 do

valid = comb(nines[i],valid,set_size)

--if floor(count_empties(nines[i])/2)>=set_size then -- (untested)

--end if

valid = comb(nines[i],valid,set_size)

end for

--end if

end for

end for

--

end for

--

-- 3) x-wings

-- ~~3) x-wings~~

--

for ch='1' to '9' do

--

sequence prevsets = repeat(0,9), set

for ch='1' to '9' do

integer count, idx

prevsets = repeat(0,9)

for x=1 to 9 do

for x=1 to 9 do

count = 0

count = 0

set = repeat(0,9)

set = repeat(0,9)

for y=0 to 8 do

for y=0 to 8 do

idx = y*9+x

idx = y*9+x

if sequence(valid[idx]) and find(ch,valid[idx]) then

if sequence(valid[idx]) and find(ch,valid[idx]) then

set[y+1] = 1

set[y+1] = 1

count += 1

count += 1

end if

end if

end for

end for

if count=2 then

if count=2 then

k = find(set,prevsets)

k = find(set,prevsets)

if k!=0 then

if k!=0 then

for y=0 to 8 do

for y=0 to 8 do

if set[y+1]=1 then

if set[y+1]=1 then

for sx=1 to 9 do

for sx=1 to 9 do

if sx!=k and sx!=x then

if sx!=k and sx!=x then

valid = eliminate_in(valid,{y*9+sx},ch)

valid = eliminate_in(valid,{y*9+sx},ch)

end if

end if

end for

end for

end if

end if

end for

end for

else

else

prevsets[x] = set

prevsets[x] = set

end if

end if

end if

end for

end for

prevsets = repeat(0,9)

prevsets = repeat(0,9)

for y=0 to 8 do

for y=0 to 8 do

count = 0

count = 0

set = repeat(0,9)

set = repeat(0,9)

for x=1 to 9 do

for x=1 to 9 do

idx = y*9+x

idx = y*9+x

if sequence(valid[idx]) and find(ch,valid[idx]) then

if sequence(valid[idx]) and find(ch,valid[idx]) then

set[x] = 1

set[x] = 1

count += 1

count += 1

end if

end if

end for

end for

if count=2 then

if count=2 then

k = find(set,prevsets)

k = find(set,prevsets)

if k!=0 then

if k!=0 then

for x=1 to 9 do

for x=1 to 9 do

if set[x]=1 then

if set[x]=1 then

for sy=0 to 8 do

for sy=0 to 8 do

if sy+1!=k and sy!=y then

if sy+1!=k and sy!=y then

valid = eliminate_in(valid,{sy*9+x},ch)

valid = eliminate_in(valid,{sy*9+x},ch)

end if

end if

end for

end for

end if

end if

end for

end for

else

else

prevsets[y+1] = set

prevsets[y+1] = set

end if

end if

end if

end for

end for

end for

end for

return valid

return valid

end function

end function

function permitted_in(string board, sequence sets, valid, integer ch)

function permitted_in(string board, sequence sets, sequence valid, integer ch)

for i=1 to 9 do

sequence set

sequence set = nines[sets[i]]

integer pos, idx, bch

integer pos = 0

for i=1 to 9 do

for j=1 to 9 do

set = nines[sets[i]]

integer idx = set[j],

pos = 0

bch = board[idx]

for j=1 to 9 do

if bch>'0' then

idx = set[j]

if bch=ch then pos = -1 exit end if

bch = board[idx]

elsif find(ch,valid[idx]) then

if bch>'0' then

if pos!=0 then pos = -1 exit end if

if bch=ch then pos = -1 exit end if

pos = idx

elsif find(ch,valid[idx]) then

~~if pos!~~=0 ~~then~~ ~~pos~~ = ~~-1 exit end~~ if

end if

end for

pos = idx

if pos>0 then

end if

board[pos] = ch

end for

improved = 1

if pos>0 then

end if

board[pos] = ch

end for

improved = 1

return board

end if

end function

end for

return board

enum INVALID = -1, INCOMPLETE = 0, SOLVED = 1, MULTIPLE = 2, BRUTE = 3

end function

function plain_logic(string board)

enum INVALID = -1, INCOMPLETE = 0, SOLVED = 1, MULTIPLE = 2, BRUTE = 3

--

-- Responsible for:

function plain_logic(string board)

-- 1) cells with only one option

--

-- 2) numbers with only one home

-- Responsible for:

--

-- 1) cells with only one option

integer solved

-- 2) numbers with only one home

sequence valid = {}

--

while true do

integer solved

solved = SOLVED

sequence valid = {}

improved = 0

object vi

valid = deep_logic(board,valid)

while 1 do

-- 1) cells with only one option:

solved = SOLVED

for i=1 to length(valid) do

improved = 0

object vi = valid[i]

valid = deep_logic(board,valid)

if string(vi) then

if length(vi)=0 then return {board,{},INVALID} end if

-- 1) cells with only one option:

if length(vi)=1 then

for i=1 to length(valid) do

board[i] = vi[1]

vi = valid[i]

improved = 1

if string(vi) then

if ~~length(vi)~~=0 ~~then~~ ~~return~~ ~~{board,{},INVALID} end~~ if

end if

if length(vi)=1 then

if board[i]<='0' then

board[i] = vi[1]

solved = INCOMPLETE

improved = 1

end if

end if

end for

end if

if solved=SOLVED then return {board,{},SOLVED} end if

if board[i]<='0' then

solved = INCOMPLETE

-- 2) numbers with only one home

end if

for ch='1' to '9' do

end for

board = permitted_in(board,cols,valid,ch)

if solved=SOLVED then return {board,{},SOLVED} end if

board = permitted_in(board,rows,valid,ch)

board = permitted_in(board,squares,valid,ch)

-- 2) numbers with only one home

end for

for ch='1' to '9' do

if not improved then exit end if

board = permitted_in(board,cols,valid,ch)

end while

board = permitted_in(board,rows,valid,ch)

return {board,valid,solved}

board = permitted_in(board,squares,valid,ch)

end function

end for

if not improved then exit end if

function validate(string board)

end while

-- (sum9 should be sufficient - if you want, get rid of nine/nines)

return {board,valid,solved}

integer ch, sum9

end function

sequence nine, nines = tagset(9)

function validate(string board)

for x=0 to 8 do -- columns

-- (sum9 should be sufficient - if you want, get rid of nine/nines)

sum9 = 0

integer ch, sum9

nine = repeat(0,9)

sequence nine, nines = tagset(9)

for y=1 to 81 by 9 do

ch = board[y+x]-'0'

for x=0 to 8 do -- columns

if ch<1 or ch>9 then return false end if

sum9 = 0

sum9 += ch

nine = repeat(0,9)

nine[ch] = ch

for y=1 to 81 by 9 do

end for

ch = board[y+x]-'0'

if sum9!=45 then return false end if

if ch<1 or ch>9 then return 0 end if

if nine!=nines then return false end if

sum9 += ch

end for

nine[ch] = ch

for y=1 to 81 by 9 do -- rows

end for

sum9 = 0

if sum9!=45 then return 0 end if

nine = repeat(0,9)

if nine!=nines then return 0 end if

for x=0 to 8 do

end for

ch = board[y+x]-'0'

for y=1 to 81 by 9 do -- rows

sum9 += ch

sum9 = 0

nine[ch] = ch

nine = repeat(0,9)

end for

for x=0 to 8 do

if sum9!=45 then return false end if

ch = board[y+x]-'0'

if nine!=nines then return false end if

sum9 += ch

end for

nine[ch] = ch

for y=0 to 8 by 3 do -- small squares

end for

for x=0 to 8 by 3 do

if sum9!=45 then return 0 end if

sum9 = 0

if nine!=nines then return 0 end if

nine = repeat(0,9)

end for

for sy=y*9 to y*9+18 by 9 do

for y=0 to 8 by 3 do -- small squares

for sx=x to x+2 do

for x=0 to 8 by 3 do

ch = board[sy+sx+1]-'0'

sum9 = 0

sum9 += ch

nine = repeat(0,9)

nine[ch] = ch

for sy=y*9 to y*9+18 by 9 do

~~for~~ sx=x to ~~x+2~~ do

end for

ch = board[sy+sx+1]-'0'

if sum9!=45 then return false end if

sum9 += ch

if nine!=nines then return false end if

nine[ch] = ch

end for

end for

end for

end for

return true

if sum9!=45 then return 0 end if

end function

if nine!=nines then return 0 end if

end for

function solve(string board)

end for

{sequence solution, sequence valid, integer solved} = plain_logic(board)

return 1

if solved=INVALID then return {{},INVALID} end if

end function

if solved=SOLVED then return {{solution},SOLVED} end if

if solved=BRUTE then return {{solution},BRUTE} end if

function solve(string board, sequence valid={})

if solved!=INCOMPLETE then ?9/0 end if

sequence solution, solutions

-- find the cell with the fewest options:

integer solved

-- (a possible improvement here would be to select the shortest

integer minopt, mindx

-- with the "most pairs" set, see swordfish etc above.)

object vi

integer minopt = 10, mindx

{solution,valid,solved} = plain_logic(board)

for i=1 to 9*9 do

if solved=INVALID then return {{},INVALID} end if

object vi = valid[i]

if solved=SOLVED then return {{solution},SOLVED} end if

if string(vi) then

if solved=BRUTE then return {{solution},BRUTE} end if

if length(vi)<=1 then ?9/0 end if -- should be caught above

if solved!=INCOMPLETE then ?9/0 end if

if length(vi)<minopt then

-- find the cell with the fewest options:

minopt = length(vi)

-- (a possible improvement here would be to select the shortest

mindx = i

-- with the "most pairs" set, see swordfish etc above.)

end if

minopt = 10

end if

for i=1 to 9*9 do

end for

vi = valid[i]

sequence solutions = {}

if string(vi) then

for i=1 to minopt do

if length(vi)<=1 then ?9/0 end if -- should be caught above

board[mindx] = valid[mindx][i]

if length(vi)<minopt then

{solution,solved} = solve(board)

minopt = length(vi)

if solved=MULTIPLE then

mindx = i

return {solution,MULTIPLE}

end if

elsif solved=SOLVED

end if

or solved=BRUTE then

end for

if not find(solution[1],solutions)

solutions = {}

and validate(solution[1]) then

for i=1 to minopt do

solutions = append(solutions,solution[1])

board[mindx] = valid[mindx][i]

end if

{solution,solved} = solve(board,valid)

if length(solutions)>1 then

if solved=MULTIPLE then

return {solutions,MULTIPLE}

return {solution,MULTIPLE}

elsif length(solutions) then

elsif solved=SOLVED

return {solutions,BRUTE}

or solved=BRUTE then

end if

if not find(solution[1],solutions)

end if

and validate(solution[1]) then

end for

solutions = append(solutions,solution[1])

if length(solutions)=1 then

end if

return {solutions,BRUTE}

if length(solutions)>1 then

end if

return {solutions,MULTIPLE}

return {{},INVALID}

elsif length(solutions) then

end function

return {solutions,BRUTE}

end if

function test_one(string board)

end if

{sequence solutions, integer solved} = solve(board)

end for

string solution, desc

if length(solutions)=1 then

if solved=SOLVED then

return {solutions,BRUTE}

desc = "(logic)"

end if

elsif solved=BRUTE then

return {{},INVALID}

desc = "(brute force)"

end function

else

desc = "???" -- INVALID/INCOMPLETE/MULTIPLE

function test_one(string board)

end if

sequence solutions

if length(solutions)=0 then

string solution, desc

solution = board

integer solved

desc = "*** NO SOLUTIONS ***"

{solutions,solved} = solve(board)

elsif length(solutions)=1 then

if solved=SOLVED then

solution = solutions[1]

desc = "(logic)"

if not validate(solution) then

elsif solved=BRUTE then

desc = "*** ERROR ***" -- (should never happen)

desc = "(brute force)"

end if

else

else

desc = "???" -- INVALID/INCOMPLETE/MULTIPLE

solution = board

end if

desc = "*** MULTIPLE SOLUTIONS ***"

if length(solutions)=0 then

end if

solution = board

return {solution,desc}

desc = "*** NO SOLUTIONS ***"

end function

elsif length(solutions)=1 then

solution = solutions[1]

--NB Blank cells can be represented by any character <'1'. Spaces are not recommended since

if not validate(solution) then

-- they can all too easily be converted to tabs by copy/paste/save. In particular, ? and

desc = "*** ERROR ***" -- (should never happen)

-- _ are NOT valid characters for representing a blank square. Use any of .0-* instead.

end if

~~else~~

constant tests = {

solution = board

"..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9", -- (0.01s, (logic))

desc = "*** MULTIPLE SOLUTIONS ***"

-- row/col elimination (was 8s w/o logic first)

end if

"000000036840000000000000020000203000010000700000600400000410050003000200600000000", -- (0.04s, (brute force))

return {solution,desc}

".......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7.....", -- (1.12s, (brute force))

end function

"000037600000600090008000004090000001600000009300000040700000800010009000002540000", -- (0.00s, (logic))

"....839..1......3...4....7..42.3....6.......4....7..1..2........8...92.....25...6", -- (0.04s, (brute force))

--NB Blank cells can be represented by any character <'1'. Spaces are not recommended since

"..1..5.7.92.6.......8...6...9..2.4.1.........3.4.8..9...7...3.......7.69.1.8..7..", -- (0.00s, (logic))

-- they can all too easily be converted to tabs by copy/paste/save. In particular, ? and

-- (the following takes ~8s when checking for multiple solutions)

-- _ are NOT valid characters for representing a blank square. Use any of .0-* instead.

"--3------4---8--36--8---1---4--6--73---9----------2--5--4-7--686--------7--6--5--", -- (0.01s, (brute force))

"..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3..", -- (0.00s, (logic))

constant tests = {

"--4-5--6--6-1--8-93----7----8----5-----4-3-----6----7----2----61-5--4-3--2--7-1--", -- (0.00s, (logic))

"..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9", -- (0.01s, (logic))

-- x-wings

-- row/col elimination (was 8s w/o logic first)

".4398.25.6..425...2....1.949....4.7.3..6.8...41.2.9..382.5.........4...553489.71.", -- (0.00s, (logic))

"000000036840000000000000020000203000010000700000600400000410050003000200600000000", -- (0.04s, (brute force))

".......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7.....", -- (1.~~12s~~, (~~brute force~~))

".9...4..7.....79..8........4.58.....3.......2.....97.6........4..35.....2..6...8.", -- (0.00s, (logic))

-- "AL Escargot", so-called "hardest sudoku"

"000037600000600090008000004090000001600000009300000040700000800010009000002540000", -- (0.00s, (logic))

"....~~839~~..1......3...4....7..42.3....6.......4....7..1..2........8...92.....~~25...6~~", -- (0.~~04s~~, (brute force))

"1....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3..", -- (0.26s, (brute force))

"..1..5.7.92.6.......8...6...9..2.4.1.........3.4.8..9...7...3.......7.69.1.8..7..", -- (0.~~00s~~, (~~logic~~))

"12.3....435....1....4........54..2..6...7.........8.9...31..5.......9.7.....6...8", -- (0.48s, (brute force))

"12.4..3..3...1..5...6...1..7...9.....4.6.3.....3..2...5...8.7....7.....5.......98", -- (1.07s, (brute force))

-- (the following takes ~8s when checking for multiple solutions)

"394..267....3..4..5..69..2..45...9..6.......7..7...58..1..67..8..9..8....264..735", -- (0.00s, (logic))

"--3------4---8--36--8---1---4--6--73---9----------2--5--4-7--686--------7--6--5--", -- (0.01s, (brute force))

"..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3..", -- (0.~~00s~~, (~~logic~~))

"4......6.5...8.9..3....1....2.7....1.9.....4.8....3.5....2....7..6.5...8.1......6", -- (0.01s, (brute force))

"5...7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79", -- (0.00s, (logic))

"--4-5--6--6-1--8-93----7----8----5-----4-3-----6----7----2----61-5--4-3--2--7-1--", -- (0.00s, (logic))

"503600009010002600900000080000700005006804100200003000030000008004300050800006702", -- (0.00s, (logic))

-- x-wings

".~~4398.25~~.6.~~.425~~...2....1.~~949~~....4.7.3..6.8...41.2.9..~~382~~.5.........4...~~553489~~.71.", -- (0.00s, (logic))

"53..247....2...8..1..7.39.2..8.72.49.2.98..7.79.....8.....3.5.696..1.3...5.69..1.", -- (0.00s, (logic))

"530070000600195000098000060800060003400803001700020006060000280000419005000080079", -- (0.00s, (logic))

".9...4..7.....79..8........4.58.....3.......2.....97.6........4..35.....2..6...8.", -- (0.00s, (logic))

-- set exclusion

-- "AL Escargot", so-called "hardest sudoku"

"1....7.9..3..2...8..96..5....53..9...1..8...26....4...3.....~~.1..4......7..7.~~..3..", -- (0.~~26s~~, (~~brute force~~))

"75..9..46961...3524.....79.2..6.1..7.8.....2.1..328.65.........3.9...2.484..3..79", -- (0.00s, (logic))

-- Worlds hardest sudoku:

"12.3....435....1....4........54..2..6...7.........8.9...31..5.......9.7.....6...8", -- (0.48s, (brute force))

"800000000003600000070090200050007000000045700000100030001000068008500010090000400", -- (0.21s, (brute force))

"12.4..3..3...1..5...6...1..7...9.....4.6.3.....3..2...5...8.7....7.....5.......98", -- (1.07s, (brute force))

"819--5-----2---75--371-4-6-4--59-1--7--3-8--2--3-62--7-5-7-921--64---9-----2--438", -- (0.00s, (logic))

"394..267....3..4..5..69..2..45...9..6.......7..7...58..1..67..8..9..8....264..735", -- (0.00s, (logic))

"4......6.5...8.9..3....1....2.7....1.9.....4.8....3.5....2....7..6.5...8.1......6", -- (0.01s, (~~brute force~~))

"85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4.", -- (0.01s, (logic))

"5...7....6..~~195~~....98....6.8...6...34..8.3..17...2...6.6....28....~~419~~..5....8..79", -- (0.~~00s~~, (~~logic~~))

"9..2..5...4..6..3...3.....6...9..2......5..8...7..4..37.....1...5..2..4...1..6..9", -- (0.17s, (brute force))

"97.3...6..6.75.........8.5.......67.....3.....539..2..7...25.....2.1...8.4...73..", -- (0.00s, (logic))

"503600009010002600900000080000700005006804100200003000030000008004300050800006702", -- (0.00s, (logic))

-- "the beast" (an earlier algorithm took 318s (5min 18s) on this):

"53..247....2...8..1..7.39.2..8.72.49.2.98..7.79.....8.....3.5.696..1.3...5.69..1.", -- (0.00s, (logic))

"000060080020000000001000000070000102500030000000000400004201000300700600000000050", -- (0.03s, (brute force))

"530070000600195000098000060800060003400803001700020006060000280000419005000080079", -- (0.00s, (logic))

$},

-- set exclusion

"75..9..46961...3524.....79.2..6.1..7.8.....2.1..328.65.........3.9...2.484..3..79", -- (0.00s, (logic))

lt = length(tests),

-- Worlds hardest sudoku:

run_one_test = 0

"800000000003600000070090200050007000000045700000100030001000068008500010090000400", -- (0.21s, (brute force))

"819--5-----2---75--371-4-6-4--59-1--7--3-8--2--3-62--7-5-7-921--64---9-----2--438", -- (0.00s, (logic))

constant l = " x x x | x x x | x x x ",

"85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4.", -- (0.01s, (logic))

s = "-------+-------+-------",

"9..2..5...4..6..3...3.....6...9..2......5..8...7..4..37.....1...5..2..4...1..6..9", -- (0.17s, (brute force))

l3 = join({l,l,l},"\n"),

"97.3...6..6.75.........8.5.......67.....3.....539..2..7...25.....2.1...8.4...73..", -- (0.00s, (logic))

fmt = substitute(join({l3,s,l3,s,l3},"\n"),"x","%c")&"\n"

-- "the beast" (an earlier algorithm took 318s (5min 18s) on this):

"000060080020000000001000000070000102500030000000000400004201000300700600000000050", -- (0.03s, (brute force))

procedure test()

$},

string board, -- (81 characters)

solution, desc

lt = length(tests),

atom t0 = time()

run_one_test = 0

if run_one_test then

board = tests[run_one_test]

constant l = " x x x | x x x | x x x ",

printf(1,fmt,board)

s = "-------+-------+-------",

{solution,desc} = test_one(board)

l3 = join({l,l,l},"\n"),

if length(solution)!=0 then

fmt = substitute(join({l3,s,l3,s,l3},"\n"),"x","%c")&"\n"

printf(1,"solution:\n")

printf(1,fmt,solution)

procedure print_board(string board)

end if

printf(1,fmt,board)

printf(1,"%s, %3.2fs\n",{desc,time()-t0})

end procedure

else

for i=1 to lt do

procedure test()

atom t1 = time()

string board -- (81 characters)

board = tests[i]

string solution, desc

{solution,desc} = test_one(board)

atom t0 = time()

printf(1," \"%s\", -- (%3.2fs, %s)\n",{board,time()-t1,desc})

if run_one_test then

-- printf(1," \"%s\", -- (%3.2fs, %s)\n",{solution,time()-t1,desc})

board = tests[run_one_test]

end for

print_board(board)

t0 = time()-t0

{solution,desc} = test_one(board)

printf(1,"%d puzzles solved in %3.2fs (av %3.2fs)\n",{lt,t0,t0/lt})

if length(solution)!=0 then

end if

printf(1,"solution:\n")

end procedure

print_board(solution)

test()

end if

printf(1,"%s, %3.2fs\n",{desc,time()-t0})

else

for i=1 to lt do

atom t1 = time()

board = tests[i]

{solution,desc} = test_one(board)

printf(1," \"%s\", -- (%3.2fs, %s)\n",{board,time()-t1,desc})

-- printf(1," \"%s\", -- (%3.2fs, %s)\n",{solution,time()-t1,desc})

end for

t0 = time()-t0

printf(1,"%d puzzles solved in %3.2fs (av %3.2fs)\n",{lt,t0,t0/lt})

end if

end procedure

test()</lang>

<pre>