
Continue on to Prolog. Now I remember what impression I had on prolog — it is not really a programming language, rather it is an application to solve logic problems. There are facts and rules, but no algorithm. Well, you know there are always algorithms for computer to do anything. The algorithm must has been built into the compilers. Then immediately I have this question, how do we ensure the algorithm will be optimal? I guess whether an algorithm is optimal or not is for programmers, not really for application users. Applications are fine, they let us focus on what we need to do.
In prolog, the algorithm probably is just enumeration. It has to be, right? If prolog is a programming language, should it belong to the same family as flex and yacc?
Anyway, the book has an example of solving sudoku. I had wrote similar program in perl a few years ago. I’ll dig that code up and present it in my macro system and compare with that prolog version.
Here is the code in prolog (following the Author’s 4×4 example):
valid([]).
valid([Head|Tail]) :-
fd_all_different(Head),
valid(Tail).
sudoku(Puzzle, Solution) :-
Solution = Puzzle,
Puzzle = [S11, S12, S13, S14, S15, S16, S17, S18, S19,
S21, S22, S23, S24, S25, S26, S27, S28, S29,
S31, S32, S33, S34, S35, S36, S37, S38, S39,
S41, S42, S43, S44, S45, S46, S47, S48, S49,
S51, S52, S53, S54, S55, S56, S57, S58, S59,
S61, S62, S63, S64, S65, S66, S67, S68, S69,
S71, S72, S73, S74, S75, S76, S77, S78, S79,
S81, S82, S83, S84, S85, S86, S87, S88, S89,
S91, S92, S93, S94, S95, S96, S97, S98, S99],
fd_domain(Solution, 1, 9),
Row1 = [S11, S12, S13, S14, S15, S16, S17, S18, S19],
Row2 = [S21, S22, S23, S24, S25, S26, S27, S28, S29],
Row3 = [S31, S32, S33, S34, S35, S36, S37, S38, S39],
Row4 = [S41, S42, S43, S44, S45, S46, S47, S48, S49],
Row5 = [S51, S52, S53, S54, S55, S56, S57, S58, S59],
Row6 = [S61, S62, S63, S64, S65, S66, S67, S68, S69],
Row7 = [S71, S72, S73, S74, S75, S76, S77, S78, S79],
Row8 = [S81, S82, S83, S84, S85, S86, S87, S88, S89],
Row9 = [S91, S92, S93, S94, S95, S96, S97, S98, S99],
Col1 = [S11, S21, S31, S41, S51, S61, S71, S81, S91],
Col2 = [S12, S22, S32, S42, S52, S62, S72, S82, S92],
Col3 = [S13, S23, S33, S43, S53, S63, S73, S83, S93],
Col4 = [S14, S24, S34, S44, S54, S64, S74, S84, S94],
Col5 = [S15, S25, S35, S45, S55, S65, S75, S85, S95],
Col6 = [S16, S26, S36, S46, S56, S66, S76, S86, S96],
Col7 = [S17, S27, S37, S47, S57, S67, S77, S87, S97],
Col8 = [S18, S28, S38, S48, S58, S68, S78, S88, S98],
Col9 = [S19, S29, S39, S49, S59, S69, S79, S89, S99],
Sqr11 = [S11, S12, S13, S21, S22, S23, S31, S32, S33],
Sqr12 = [S14, S15, S16, S24, S25, S26, S34, S35, S36],
Sqr13 = [S17, S18, S19, S27, S28, S29, S37, S38, S39],
Sqr21 = [S41, S42, S43, S51, S52, S53, S61, S62, S63],
Sqr22 = [S44, S45, S46, S54, S55, S56, S64, S65, S66],
Sqr23 = [S47, S48, S49, S57, S58, S59, S67, S68, S69],
Sqr31 = [S71, S72, S73, S81, S82, S83, S91, S92, S93],
Sqr32 = [S74, S75, S76, S84, S85, S86, S94, S95, S96],
Sqr33 = [S77, S78, S79, S87, S88, S89, S97, S98, S99],
valid([Row1, Col1, Row2, Col2, Row3, Col3, Row4, Col4, Row5, Col5, Row6, Col6, Row7, Col7, Row8, Col8, Row9, Col9, Sqr11, Sqr12, Sqr13, Sqr21, Sqr22, Sqr23, Sqr31, Sqr32, Sqr33]).
As any application, we just need to describe the problem. However, not having full features of general programming languages, even describing the problems can be cumbersome. The predicates fd_all_different and fd_domain certainly helps. There are many more predicates implemented in gnu prolog and some of them probably exist so describe the rules for a 100×100 sudoku problems can be possible. But as you go through the list of available predicates, you probably will have have the feeling of learning a new application, rather than learning a language.
I actually wrote a perl script to output this prolog code, so it is not so much trouble for me to do 100×100 sudoku in prolog if I have to.
Here is running the program:
$ gplc sudoku9.pro
$ ./sudoku9
GNU Prolog 1.3.1
By Daniel Diaz
Copyright (C) 1999-2009 Daniel Diaz
| ?- sudoku([4,_,_,_,_,_,_,_,_, 6,5,_,_,7,2,_,_,8, _,_,1,_,9,3,_,5,4, 7,_,_,8,3,1,9,_,5, 9,_,_,_,_,_,_,_,1, 3,_,2,9,5,4,_,_,7, 1,4,_,3,6,_,5,_,_, 5,_,_,2,1,_,_,8,6, _,_,_,_,_,_,_,_,3], Solution).
Solution = [4,_#16(2..3:7:9),_#37(3:7:9),1,8,5, _#121(2..3:6..7),_#142(3:7:9),_#163(2:9), 6,5,_#210(3:9),4,7,2,_#278(1:3),_#299(1:3:9),8, _#333(2:8),_#354(2:7),1,6,9,3,_#435(2:7),5,4, 7,6,4,8,3,1,9,2,5, 9,8,5,7,2,6,_#741(3..4),_#762(3..4),1, 3,1,2,9,5,4,8,6,7, 1,4,_#963(7..9),3,6,_#1010(7..9),5,_#1044(7:9),_#1065(2:9), 5,_#1099(3:7:9),_#1120(3:7:9),2,1,_#1167(7:9),_#1188(4:7),8,6, _#1235(2:8),_#1256(2:7:9),_#1277(6..9), 5,4,_#1340(7..9),_#1361(1..2:7),_#1382(1:7:9),3]
Kind of disappointing that it didn’t give us the final answer. There probably are some thing in the menu to explain how to get a usable solution, just more learning. I am too old for that.
Here is my perl program written in my macro system:
page
: sudoku
subcode
: main
# Input
my $t=$ARGV[0]
# Workspace is an array of 9x9x(1+9+1) array
# $l=($i*9+$j)*11
# $work->[$l] : answer for that cell
# $work->[$l+$k+1]: possible answer $k for that cell
# $work->[$l+$k+10]: number of possible answers
my $work=[];
# The program uses check1 and check2 subroutine
# just as how we solve a sudoku problem manually,
# but if failed, it has to resolve to bruteforce
# trial
my @trystack;
# Maximum trial recursion levels.
# You don’t want it to run forever.
my $maxlevel=100;
$call initialize
print_result()
trysolve(0)
# There are only two perl functions.
# We can use more if that is desired
$list trysolve, print_result
# Master solver
fncode: trysolve
my $level=shift;
my $flag_updated=1
my $flag_done=0
my $flag_failed=0
$while $flag_updated
$flag_updated=0
$flag_done=1
# Any cell with only 1 possible number left?
$call check1
# Any number with only 1 possible cell left?
$call check2
$if $flag_done
# I havn’t try much, but those I have tried
# got a solution here if it has unique solution
print_result()
$if !$flag_done and !$flag_failed
$if $level<$maxlevel
# Pick a cell, choose one possible number,
# push the rest to stack
$call try
trysolve($level+1)
$elif !$flag_failed
print_result()
$elif $work=pop @trystack
# Try solve the other case.
trysolve($level+1)
# ————————————————————-
# See how clear a procedural code can be. The rest
# are quite similar to how we specify the rules in
# prolog. We need describe how do we access a row,
# a col, and a grid, how to elliminate possible
# answers and how to set an answer.As long as we
# understand the general logic, the rest of the code
# does not need much comments.
# ————————————————————-
subcode: initialize
my @tlist=split /,\s*/, $t
&call each_cell
$work->[$l+10]=9
$for $k=0:9
$work->[$l+$k+1]=1
&call each_cell
my $t=shift @tlist
$if $t ne "_"
$t-=1
$call setcell
subcode: check1
$flag_updated=1
$while $flag_updated
$flag_updated=0
$flag_done=1
&call each_cell
$if !defined $work->[$l]
$flag_done=0
$if $work->[$l+10]==0
$flag_failed=1
$elif $work->[$l+10]==1
$for $k=0:9
$if $work->[$l+$k+1]
my $t=$k
$call setcell
last
subcode: check2
$for $k=0:9
$(for:dir in row,col,grid)
&call each_$(dir)
my $cnt=0
my $first
&call each_$(dir)_cell
$if !defined $work->[$l] and $work->[$l+$k+1]
$first=$l
$cnt++
$if $cnt==1
$t=$k;
$l=$first
$call l_to_ij
$call setcell
subcode: try
my $try_l;
my $try_k;
&call each_cell
$if !defined $work->[$l]
$for $k=0:9
$if !defined $try_l and $work->[$l+$k+1]
$try_l=$l
$try_k=$k
$if $try_l
my $l=$try_l
my $t=$try_k
my @workcopy=@$work
$workcopy[$l+$t+1]=0
push @trystack, \@workcopy
$call l_to_ij
$call setcell
# ————————————-
subcode: setcell
$work->[$l]=$t
$(for:dir in row,col,grid)
&call each_neighbor_$(dir)
$if $work->[$ll+$t+1]
$work->[$ll+$t+1]=0
$work->[$ll+10]–
$flag_updated=1
# ————————————-
subcode: each_cell
$l=0;
$for $i=0:9
$for $j=0:9
BLOCK
$l+=11
subcode: each_neighbor_row
my $ll=($i*9)*11
$for $k=0:9
BLOCK
$ll+=11
subcode: each_neighbor_col
my $ll=$j*11
$for $k=0:9
BLOCK
$ll+=9*11
subcode: each_neighbor_grid
my $i1=int($i/3)
my $j1=int($j/3)
$for $i2=0:3
$for $j2=0:3
my $ll=(($i1*3+$i2)*9+$j1*3+$j2)*11
BLOCK
subcode: each_row
$for $i=0:9
BLOCK
subcode: each_row_cell
$for $j=0:9
my $l=($i*9+$j)*11
BLOCK
subcode: each_col
$for $j=0:9
BLOCK
subcode: each_col_cell
$for $i=0:9
my $l=($i*9+$j)*11
BLOCK
subcode: each_grid
$for $i1=0:3
$for $j1=0:3
BLOCK
subcode: each_grid_cell
$for $i2=0:3
$for $j2=0:3
my $l=(($i1*3+$i2)*9+$j1*3+$j2)*11
BLOCK
subcode: l_to_ij
my $i=int($l/11/9)
my $j=int($l/11)%9
# ————————————-
fncode: print_result
&call each_row
&call each_row_cell
$if defined $work->[$l]
print $work->[$l]+1, " ";
$else
print "_ ";
print "\n";
print "——————————-\n";
And here is how it runs:
$
make
mydef_page.pl sudoku.def sudoku.pl
PAGE: sudoku
–
> [.
/sudoku.pl
]
$ perl sudoku.pl "4,_,_,_,_,_,_,_,_, 6,5,_,_,7,2,_,_,8, _,_,1,_,9,3,_,5,4, 7,_,_,8,3,1,9,_,5, 9,_,_,_,_,_,_,_,1, 3,_,2,9,5,4,_,_,7, 1,4,_,3,6,_,5,_,_, 5,_,_,2,1,_,_,8, 6,_,_,_,_,_,_,_,_,3"
4 _ _ _ _ _ _ _ _
6 5 _ _ 7 2 _ _ 8
_ _ 1 _ 9 3 _ 5 4
7 _ _ 8 3 1 9 _ 5
9 _ _ _ _ _ _ _ 1
3 _ 2 9 5 4 _ _ 7
1 4 _ 3 6 _ 5 _ _
5 _ _ 2 1 _ _ 8 6
_ _ _ _ _ _ _ _ 3
——————————-
4 2 3 1 8 5 6 7 9
6 5 9 4 7 2 1 3 8
8 7 1 6 9 3 2 5 4
7 6 4 8 3 1 9 2 5
9 8 5 7 2 6 3 4 1
3 1 2 9 5 4 8 6 7
1 4 8 3 6 7 5 9 2
5 3 7 2 1 9 4 8 6
2 9 6 5 4 8 7 1 3
——————————-
$