Solving sudoku by postscript.
/# {load def} bind def | |
/! {exch def} bind def | |
/M/moveto #/L/lineto #/RM/rmoveto #/RL/rlineto # | |
/s/stroke #/f/fill #/S/show #/CP/closepath # | |
/sudokuDict 256 dict def | |
sudokuDict begin | |
[ | |
%------------ Write the problem here --------------- | |
[[ ] [6] [1] [ ] [ ] [7] [ ] [ ] [3]] | |
[[ ] [9] [2] [ ] [ ] [3] [ ] [ ] [ ]] | |
[[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]] | |
[[ ] [ ] [8] [5] [3] [ ] [ ] [ ] [ ]] | |
[[ ] [ ] [ ] [ ] [ ] [ ] [5] [ ] [4]] | |
[[5] [ ] [ ] [ ] [ ] [8] [ ] [ ] [ ]] | |
[[ ] [4] [ ] [ ] [ ] [ ] [ ] [ ] [1]] | |
[[ ] [ ] [ ] [1] [6] [ ] [8] [ ] [ ]] | |
[[6] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]] | |
%--------------------------------------------------- | |
] | |
/board ! | |
/len/length #/g/get #/x/exch #/clr/cleartomark # | |
/id { } bind def | |
/head { 0 get } bind def | |
/map { [ 3 1 roll forall ] } def | |
/adup { { id } map } bind def | |
/filter { | |
[ 3 1 roll x { 2 copy x mark 3 1 roll exec { clr x } { clr pop } ifelse } forall pop ] | |
} def | |
/seq { [ 3 1 roll 1 x { } for ] } def | |
/arg { | |
dup len | |
mark | |
1 index 3 add 1 roll | |
1 sub dup 0 x seq | |
{ | |
dup 3 index x | |
get x | |
2 index x sub | |
3 add index | |
def | |
} forall | |
clr | |
} def | |
/applyAtDict 3 dict def | |
/applyAt | |
{ | |
applyAtDict begin | |
[/ary /i /proc] arg | |
ary i get proc | |
end | |
% separating namespace | |
exec | |
applyAtDict begin | |
ary x i x put | |
end | |
} def | |
/includes? | |
{ | |
2 dict begin | |
[/ary /val] arg | |
ary { val eq } map false x { or } forall | |
end | |
} def | |
/isValid | |
{ | |
1 x { len mul } forall 0 gt | |
} def | |
/isComplete | |
{ | |
dup | |
1 x { len mul } forall 1 eq | |
{ | |
dup | |
0 x { head add } forall 45 eq x | |
1 x { head mul } forall 362880 eq | |
and | |
} { pop false } ifelse | |
} def | |
/checkValid { | |
true x | |
{ isValid and } forall | |
} def | |
/perm_delete_elem_dict 3 dict def | |
/perm_delete_elems | |
{ | |
perm_delete_elem_dict begin | |
/i ! | |
/bs ! | |
bs i get 0 get | |
/v ! | |
0 bs len 1 sub seq { | |
dup bs x get | |
x i gt | |
{ { v ne } filter } | |
{ adup } | |
ifelse | |
} map | |
end | |
} def | |
/perm_main_dict 2 dict def | |
/perm_main | |
{ | |
perm_main_dict begin | |
[/lst /pos] arg | |
[ | |
lst pos get | |
{ | |
lst adup dup | |
3 -1 roll | |
[ x ] pos x | |
put | |
} forall | |
] | |
{ pos perm_delete_elems } map | |
{ isValid } filter | |
end | |
} def | |
/permutationDict 5 dict def | |
/permutation | |
{ | |
permutationDict begin | |
[/base_lst] arg | |
mark | |
base_lst len 1 sub /n ! | |
base_lst 0 | |
perm_main | |
0 0 | |
{ | |
[/lst /i /j] arg | |
j lst len lt | |
{ | |
% save context | |
lst i j 1 add | |
lst j get | |
i n lt | |
{ i 1 add perm_main i 1 add 0 } | |
{ | |
counttomark 1 add 1 roll | |
} | |
ifelse | |
} | |
{ | |
i 0 eq { exit } if | |
} | |
ifelse | |
} loop | |
clr | |
end | |
} def | |
/deepcopy { | |
{ { adup } map } map | |
} def | |
/arrayEq | |
{ | |
2 dict begin | |
[/a1 /a2] arg | |
a1 len a2 len eq | |
{ | |
true | |
0 a1 len 1 sub seq { | |
dup a1 x get x a2 x get eq | |
and | |
} forall | |
} | |
{ | |
false | |
} | |
ifelse | |
end | |
} def | |
/compareStateDict 5 dict def | |
/compareState { | |
compareStateDict begin | |
[/s1 /s2] arg | |
true | |
0 8 seq { | |
/i ! | |
s1 i get /r1 ! | |
s2 i get /r2 ! | |
true | |
0 8 seq { | |
dup r1 x get x r2 x get arrayEq | |
and | |
dup not { exit } if | |
} forall | |
and | |
dup not { exit } if | |
} forall | |
end | |
} def | |
/blk2griddict 2 dict def | |
/blk2grid { | |
blk2griddict begin | |
/j ! /i ! | |
i 3 idiv 3 mul j 3 idiv add | |
i 3 mod 3 mul j 3 mod add | |
end | |
} def | |
/extractDict 4 dict def | |
/extractBlock { | |
extractDict begin | |
/b ! | |
/cand ! | |
0 8 seq { b x blk2grid cand 3 -1 roll get x get adup } map | |
end | |
} def | |
/extractRow { | |
get { adup } map | |
} def | |
/extractColumn { | |
extractDict begin | |
/c ! | |
{ c get adup } map | |
end | |
} def | |
/replaceDict 6 dict def | |
/replaceRow { | |
replaceDict begin | |
[/brd /r /ln] arg | |
brd r get | |
0 8 seq { 2 copy 3 -1 roll ln x get put } forall | |
pop | |
end | |
} def | |
/replaceColumn { | |
replaceDict begin | |
[/brd /c /ln] arg | |
0 8 seq { dup brd x get x ln x get c x put } forall | |
end | |
} def | |
/replaceBlock { | |
replaceDict begin | |
[/brd /b /ln] arg | |
0 8 seq { | |
/j ! | |
b j blk2grid x brd x get | |
x ln j get put | |
} forall | |
end | |
} def | |
/eliminateDict 8 dict def | |
/eliminateLine { | |
[/ln] arg | |
0 8 seq { | |
/i ! | |
ln i get | |
dup len | |
1 eq | |
{ | |
0 get /v ! | |
0 8 seq { | |
/j ! | |
i j ne | |
{ | |
ln j get | |
{ v ne } filter | |
ln x j x | |
put | |
} if | |
} forall | |
} | |
{ | |
pop | |
} | |
ifelse | |
} forall | |
} def | |
/eliminateRow { | |
eliminateDict begin | |
[/cands] arg | |
0 8 seq { | |
/r ! | |
cands r extractRow dup | |
eliminateLine | |
cands x r x replaceRow | |
} forall | |
end | |
} def | |
/eliminateColumn { | |
eliminateDict begin | |
[/cands] arg | |
0 8 seq { | |
/c ! | |
cands c extractColumn dup | |
eliminateLine | |
cands x c x replaceColumn | |
} forall | |
end | |
} def | |
/eliminateBlock { | |
eliminateDict begin | |
[/cands] arg | |
0 8 seq { | |
/b ! | |
cands b extractBlock dup | |
eliminateLine | |
cands x b x replaceBlock | |
} forall | |
end | |
} def | |
/findConcreteDict 8 dict def | |
/findConcrete { | |
[/ln] arg | |
0 8 seq { pop 0 } map /cnts ! | |
0 8 seq { | |
ln x get { 1 sub cnts x { 1 add } applyAt } forall | |
} forall | |
0 8 seq { | |
/i ! | |
cnts i get 1 eq | |
{ | |
0 8 seq { | |
/j ! | |
ln j get i 1 add includes? | |
{ | |
ln j [i 1 add] put | |
} if | |
} forall | |
} if | |
} forall | |
} def | |
/fixConcreteInRows { | |
findConcreteDict begin | |
[/cands] arg | |
0 8 seq { | |
/r ! | |
cands r extractRow dup | |
findConcrete | |
cands x r x replaceRow | |
} forall | |
end | |
} def | |
/fixConcreteInColumns { | |
findConcreteDict begin | |
[/cands] arg | |
0 8 seq { | |
/c ! | |
cands c extractColumn dup | |
findConcrete | |
cands x c x replaceColumn | |
} forall | |
end | |
} def | |
/fixConcreteInBlocks { | |
findConcreteDict begin | |
[/cands] arg | |
0 8 seq { | |
/b ! | |
cands b extractBlock dup | |
findConcrete | |
cands x b x replaceBlock | |
} forall | |
end | |
} def | |
/applyHeuristicsDict 4 dict def | |
/applyHeuristics { | |
applyHeuristicsDict begin | |
[/cands] arg | |
/ret -1 def | |
1 20 seq { | |
/i ! | |
cands deepcopy /new_cands ! | |
new_cands eliminateRow | |
new_cands checkValid not { exit } if | |
new_cands eliminateColumn | |
new_cands checkValid not { exit } if | |
new_cands eliminateBlock | |
new_cands checkValid not { exit } if | |
new_cands fixConcreteInRows | |
new_cands fixConcreteInColumns | |
new_cands fixConcreteInBlocks | |
new_cands checkValid not { exit } if | |
cands new_cands compareState | |
{ | |
/ret i def | |
exit | |
} if | |
new_cands cands copy pop | |
} forall | |
ret | |
end | |
} def | |
/checkComplete { | |
1 dict begin | |
[/brd] arg | |
true 0 8 seq { brd x extractRow isComplete and } forall | |
dup | |
{ | |
0 8 seq { brd x extractColumn isComplete and } forall | |
dup | |
{ | |
0 8 seq { brd x extractBlock isComplete and } forall | |
} if | |
} | |
if | |
end | |
} def | |
/genInitialCandidates { | |
{ | |
{ | |
dup len | |
1 ge | |
{ adup } | |
{ pop 1 9 seq } | |
ifelse | |
} map | |
} map | |
} def | |
/findPivot { | |
4 dict begin | |
[/cands] arg | |
387420489 /min ! | |
0 /minRow ! | |
0 8 seq { | |
/i ! | |
1 cands i get { len mul } forall | |
dup | |
dup | |
1 gt x | |
min lt and | |
{ /min ! i /minRow ! } | |
{ pop } | |
ifelse | |
} forall | |
minRow | |
end | |
} def | |
/solveSudoku_main { | |
mark | |
0 /cnt ! | |
0 | |
cands | |
cands findPivot dup | |
cands x get | |
[ x permutation ] x | |
0 | |
{ | |
[/d /brd /perms /p /j] arg | |
j perms len lt | |
{ | |
% push current context | |
d brd perms p j 1 add | |
brd deepcopy /new_brd ! | |
new_brd p perms j get replaceRow | |
new_brd applyHeuristics 0 ge | |
{ | |
new_brd checkComplete | |
{ | |
cnt 1 add /cnt ! | |
new_brd | |
counttomark 1 add 1 roll | |
} | |
{ | |
% push new context | |
d 1 add | |
new_brd | |
new_brd findPivot dup | |
new_brd x get [ x permutation ] x | |
0 | |
} ifelse | |
} if | |
} | |
{ | |
d 0 gt not { exit } if | |
} ifelse | |
cnt 10 ge { | |
(**There are more than 10 answers of this problem!**) = | |
exit | |
} if | |
} loop | |
clr | |
} def | |
/solveSudoku { | |
16 dict begin | |
[/problem] arg | |
problem genInitialCandidates /cands ! | |
cands applyHeuristics | |
0 ge | |
{ | |
[ solveSudoku_main ] | |
} | |
{ | |
[ ] | |
} | |
ifelse | |
end | |
} def | |
/drawBoardGrid { | |
3 setlinewidth | |
0 0 M 450 0 RL 0 -450 RL -450 0 RL CP s | |
0 -150 M 450 0 RL s | |
0 -300 M 450 0 RL s | |
150 0 M 0 -450 RL s | |
300 0 M 0 -450 RL s | |
1 setlinewidth | |
0 -50 M 450 0 RL s | |
0 -100 M 450 0 RL s | |
0 -200 M 450 0 RL s | |
0 -250 M 450 0 RL s | |
0 -350 M 450 0 RL s | |
0 -400 M 450 0 RL s | |
50 0 M 0 -450 RL s | |
100 0 M 0 -450 RL s | |
200 0 M 0 -450 RL s | |
250 0 M 0 -450 RL s | |
350 0 M 0 -450 RL s | |
400 0 M 0 -450 RL s | |
} def | |
/drawBoard { | |
16 dict begin | |
[/brd /ans] arg | |
gsave | |
25 500 translate | |
drawBoardGrid | |
/Helvetica-Bold findfont 36 scalefont setfont | |
0 8 seq { | |
/i ! | |
brd i get /probRow ! | |
ans i get /ansRow ! | |
0 8 seq { | |
/j ! | |
probRow j get dup | |
len 1 eq | |
{ | |
0 get /v ! | |
50 j mul 15 add -50 i mul -40 add M | |
v ( ) cvs true charpath s | |
} | |
{ | |
pop | |
ansRow j get | |
0 get /v ! | |
50 j mul 15 add -50 i mul -40 add M | |
v ( ) cvs true charpath f | |
} | |
ifelse | |
} forall | |
} forall | |
grestore | |
end | |
} def | |
/noAnswer { | |
gsave | |
/GothicBBB-Medium-H findfont 72 scalefont setfont | |
50 700 M | |
<3272244a2437212a> show | |
grestore | |
} def | |
board solveSudoku /answers ! | |
answers len 1 ge | |
{ | |
answers len 2 ge | |
{ | |
gsave | |
/GothicBBB-Medium-H findfont 28 scalefont setfont | |
50 770 M | |
<3272242c42743b332422246a245e24392123> show | |
50 730 M | |
<245f2443244424402431493d3c282437245e24392123> show | |
grestore | |
gsave | |
50 400 translate | |
0.5 0.5 scale | |
board answers 0 get drawBoard | |
grestore | |
gsave | |
305 400 translate | |
0.5 0.5 scale | |
board answers 1 get drawBoard | |
grestore | |
answers len 2 gt | |
{ | |
gsave | |
50 50 translate | |
0.5 0.5 scale | |
board answers 2 get drawBoard | |
grestore | |
} if | |
} | |
{ | |
gsave | |
25 842 50 sub 500 sub translate | |
board answers 0 get drawBoard | |
gsave | |
} ifelse | |
showpage | |
} | |
{ | |
noAnswer | |
showpage | |
} | |
ifelse | |
end | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment