189 lines
6 KiB
Text
189 lines
6 KiB
Text
{sudokuSolver.bra
|
|
|
|
Solves any 9x9 sudoku, using backtracking.
|
|
Not a simple brute force algorithm!}
|
|
|
|
sudokuSolver=
|
|
( sudoku
|
|
= ( new
|
|
= create
|
|
. ( create
|
|
= a
|
|
. !arg:%(<3:?a) ?arg
|
|
& ( !a
|
|
. !arg:
|
|
& 1 2 3 4 5 6 7 8 9
|
|
| create$!arg
|
|
)
|
|
create$(!a+1 !arg)
|
|
|
|
|
)
|
|
& create$(0 0 0 0):?(its.Tree)
|
|
& ( init
|
|
= cell remainingCells remainingRows x y
|
|
. !arg
|
|
: ( ?y
|
|
. ?x
|
|
. (.%?cell ?remainingCells) ?remainingRows
|
|
)
|
|
& ( !cell:#
|
|
& ( !cell
|
|
. mod$(!x,3)
|
|
div$(!x,3)
|
|
mod$(!y,3)
|
|
div$(!y,3)
|
|
)
|
|
|
|
|
)
|
|
( !remainingCells:
|
|
& init$(!y+1.0.!remainingRows)
|
|
| init
|
|
$ ( !y
|
|
. !x+1
|
|
. (.!remainingCells) !remainingRows
|
|
)
|
|
)
|
|
|
|
|
)
|
|
& out$!arg
|
|
& (its.Set)$(!(its.Tree).init$(0.0.!arg))
|
|
: ?(its.Tree)
|
|
)
|
|
( Display
|
|
= val
|
|
. put$(str$("|~~~|~~~|~~~|" \n))
|
|
& !(its.Tree)
|
|
: ?
|
|
( ?
|
|
. ?
|
|
( ?&put$"|"
|
|
. ?
|
|
( ?
|
|
. ?
|
|
( ( ?
|
|
. ?val
|
|
& !val:% %
|
|
& put$"-"
|
|
| !val:
|
|
& put$" "
|
|
| put$!val
|
|
)
|
|
& ~
|
|
)
|
|
?
|
|
| ?&put$"|"&~
|
|
)
|
|
?
|
|
| ?&put$\n&~
|
|
)
|
|
?
|
|
| ?
|
|
& put$(str$("|~~~|~~~|~~~|" \n))
|
|
& ~
|
|
)
|
|
?
|
|
|
|
|
)
|
|
( Set
|
|
= update certainValue a b c d
|
|
, tree branch todo DOING loop dcba minlen len minp
|
|
. ( update
|
|
= path rempath value tr
|
|
, k z x y trc p v branch s n
|
|
. !arg:(?path.?value.?tr.?trc)
|
|
& ( !path:%?path ?rempath
|
|
& `( !tr
|
|
: ?k (!path:?p.?branch) ?z
|
|
& `( update$(!rempath.!value.!branch.!p !trc)
|
|
: ?s
|
|
& update
|
|
$ (!path !rempath.!value.!z.!trc)
|
|
: ?n
|
|
& !k (!p.!s) !n
|
|
)
|
|
| !tr
|
|
)
|
|
| !DOING:(?.!trc)&!value
|
|
| !tr:?x !value ?y
|
|
& `( !x !y
|
|
: ( ~:@
|
|
& ( !todo:? (?v.!trc) ?
|
|
& ( !v:!x !y
|
|
| out
|
|
$ (mismatch v !v "<>" x y !x !y)
|
|
& get'
|
|
)
|
|
| (!x !y.!trc) !todo:?todo
|
|
)
|
|
| % %
|
|
| &!DOING:(?.!trc)
|
|
)
|
|
)
|
|
| !tr
|
|
)
|
|
)
|
|
& !arg:(?tree.?todo)
|
|
& ( loop
|
|
= !todo:
|
|
| !todo
|
|
: ((?certainValue.%?d %?c %?b %?a):?DOING) ?todo
|
|
& update$(!a ? !c ?.!certainValue.!tree.)
|
|
: ?tree
|
|
& update$(!a !b <>!c ?.!certainValue.!tree.)
|
|
: ?tree
|
|
& update$(<>!a ? !c !d.!certainValue.!tree.)
|
|
: ?tree
|
|
& !loop
|
|
)
|
|
& !loop
|
|
& ( ~( !tree
|
|
: ?
|
|
(?.? (?.? (?.? (?.% %) ?) ?) ?)
|
|
?
|
|
)
|
|
| 9:?minlen
|
|
& :?minp
|
|
& ( len
|
|
=
|
|
. !arg:% %?arg&1+len$!arg
|
|
| 1
|
|
)
|
|
& ( !tree
|
|
: ?
|
|
( ?a
|
|
. ?
|
|
( ?b
|
|
. ?
|
|
( ?c
|
|
. ?
|
|
( ?d
|
|
. % %:?p
|
|
& len$!p:<!minlen:?minlen
|
|
& !d !c !b !a:?dcba
|
|
& !p:?:?minp
|
|
& ~
|
|
)
|
|
?
|
|
)
|
|
?
|
|
)
|
|
?
|
|
)
|
|
?
|
|
| !minp
|
|
: ?
|
|
( %@?n
|
|
& (its.Set)$(!tree.!n.!dcba):?tree
|
|
)
|
|
?
|
|
)
|
|
)
|
|
& !tree
|
|
)
|
|
(Tree=)
|
|
)
|
|
( new
|
|
= puzzle
|
|
. new$((its.sudoku),!arg):?puzzle
|
|
& (puzzle..Display)$
|
|
);
|