Seven Languages In Seven Weeks: Prolog - Day 3
Posted December 10, 2010 at 10:00 AM by Ben Nadel
Today is the last day of Prolog from my Seven Languages in Seven Weeks book. And, to be quite honest, I've had enough of Prolog. It's a very different way of thinking about programming and it seems that my brain doesn't much like to work in a way well suited for Prolog. Even after the first two assignments, today didn't feel any easier, really. And, to make matters worse, my heart just wasn't in it. As such, I didn't put my all behind these last few problems; I just wanted to get them done so that I could move on.
HW1: Modify the Sudoku solver to work on six-by-six puzzles (squares are 3x2) and 9x9 puzzles.
I only updated the solver to work on 6x6 Sudoku puzzles. Going from 6x6 to 9x9 would have just been extra work with no added value; unless, which is what I suspect, there was a way to make it more generic such that going from 6x6 to 9x9 wasn't simply "more" variables. It would have been cool to find a way to break the puzzle down into rows and columns of N length; but, my Prolog understanding isn't deep enough for that.
- %-- Modify the Sudoku solve to work on six-by-six puzzles
- %-- (squares are 3x2) and 9x9 puzzles.
-
-
- %-- This handles boards of 4x4 dimensions.
- sudoku( Puzzle, Solution ) :-
- length( Puzzle, 16 ),
- sudoku4x4( Puzzle, Solution )
- .
-
- %-- This handles boards of 6x6 dimensions.
- sudoku( Puzzle, Solution ) :-
- length( Puzzle, 36 ),
- sudoku6x6( Puzzle, Solution )
- .
-
-
- %-- I am the 4x4 solution.
- sudoku4x4( Puzzle, Solution ) :-
- %-- Assert that this is only true if the Puzzle and the
- %-- Solution are the same.
- Solution = Puzzle,
-
- %-- Break the puzzle out into variables, one for each square.
- Puzzle = [
- S11, S12, S13, S14,
- S21, S22, S23, S24,
- S31, S32, S33, S34,
- S41, S42, S43, S44
- ],
-
- %-- Assert that each element within the list (which represents
- %-- the board, is in the range 1-4).
- fd_domain( Solution, 1, 4 ),
-
- %-- Define each row as a collection of cells.
- Row1 = [S11, S12, S13, S14],
- Row2 = [S21, S22, S23, S24],
- Row3 = [S31, S32, S33, S34],
- Row4 = [S41, S42, S43, S44],
-
- %-- Define each column as a collection of cells.
- Col1 = [S11, S21, S31, S41],
- Col2 = [S12, S22, S32, S42],
- Col3 = [S13, S23, S33, S43],
- Col4 = [S14, S24, S34, S44],
-
- %-- Define each square as a collection of cells.
- Square1 = [S11, S12, S21, S22],
- Square2 = [S13, S14, S34, S24],
- Square3 = [S31, S32, S41, S42],
- Square4 = [S33, S34, S43, S44],
-
- %-- Asser that all the rows, columns, and squares are valid; that
- %-- is, they contain unique values, 1-4.
- valid([
- Row1, Row2, Row3, Row4,
- Col1, Col2, Col3, Col4,
- Square1, Square2, Square3, Square4
- ])
- .
-
-
- %-- I am the 6x6 solution.
- sudoku6x6( Puzzle, Solution ) :-
- %-- Assert that this is only true if the Puzzle and the
- %-- Solution are the same.
- Solution = Puzzle,
-
- %-- Break the puzzle out into variables, one for each square.
- Puzzle = [
- S11, S12, S13, S14, S15, S16,
- S21, S22, S23, S24, S25, S26,
- S31, S32, S33, S34, S35, S36,
- S41, S42, S43, S44, S45, S46,
- S51, S52, S53, S54, S55, S56,
- S61, S62, S63, S64, S65, S66
- ],
-
- %-- Assert that each element within the list (which represents
- %-- the board, is in the range 1-6).
- fd_domain( Solution, 1, 6 ),
-
- %-- Define each row as a collection of cells.
- Row1 = [S11, S12, S13, S14, S15, S16],
- Row2 = [S21, S22, S23, S24, S25, S26],
- Row3 = [S31, S32, S33, S34, S35, S36],
- Row4 = [S41, S42, S43, S44, S45, S46],
- Row5 = [S51, S52, S53, S54, S55, S56],
- Row6 = [S61, S62, S63, S64, S65, S66],
-
- %-- Define each column as a collection of cells.
- Col1 = [S11, S21, S31, S41, S51, S61],
- Col2 = [S12, S22, S32, S42, S52, S62],
- Col3 = [S13, S23, S33, S43, S53, S63],
- Col4 = [S14, S24, S34, S44, S54, S64],
- Col5 = [S15, S25, S35, S45, S55, S65],
- Col6 = [S16, S26, S36, S46, S56, S66],
-
- %-- Define each square as a collection of cells.
- Square1 = [S11, S21, S12, S22, S13, S23],
- Square2 = [S14, S24, S15, S25, S16, S26],
- Square3 = [S31, S41, S32, S42, S33, S43],
- Square4 = [S34, S44, S35, S45, S36, S46],
- Square5 = [S51, S61, S52, S62, S53, S63],
- Square6 = [S54, S64, S55, S65, S56, S66],
-
-
- %-- Asser that all the rows, columns, and squares are valid; that
- %-- is, they contain unique values, 1-6.
- valid([
- Row1, Row2, Row3, Row4, Row5, Row6,
- Col1, Col2, Col3, Col4, Col5, Col6,
- Square1, Square2, Square3, Square4, Square5, Square6
- ])
- .
-
-
- %-- Empty boards are valid.
- valid( [] ).
-
- %-- The sets are valid if each set contains unique values.
- valid( Sets ) :-
- (Sets = [Head|Tail]),
- fd_all_different( Head ),
- valid( Tail )
- .
I took the original sudoku() rule and changed it to be sudoku4x4(). Then, I added a sudoku6x6() rule to solve our new, 6x6 boards. Then, I went back and made the original sudoku() rules nothing more than a sort of factory for sudoku-solvers based on Puzzle length. If the board had 16 cells, sudoku() would essentially pass it off to sudoku4x4(). If the board has 36 cells, sudoku() would essentially pass it off to sudoku6x6().
Once the code was compiled, I had it solve both types of boards:
| ?- sudoku([
_,_,2,3,
_,_,_,_,
_,_,_,_,
3,4,_,_
], Solution ).
Solution = [4,1,2,3,2,3,4,1,1,2,3,4,3,4,1,2] ? a
no
| ?- sudoku([
2,1,3,_,_,_,
4,5,6,_,_,_,
_,_,_,6,1,4,
_,_,_,3,5,2,
6,4,5,_,_,_,
3,2,1,_,4,_], Solution ).
Solution = [2,1,3,4,6,5,4,5,6,_#153(1..2),_#175(2..3),_#197(1:3),5,3,2,6,
1,4,1,6,4,3,5,2,6,4,5,_#477(1..2),_#499(2..3),_#521(1:3),3,2,1,5,4,6] ? a
As you can see, I'm passing boards of variable length to the sudoku() rule and both are getting a response. What's interesting is the way that the response came back in my 6x6 board. I've never seen this before, so I'm not 100% sure what's going on; but, it looks as if Prolog has unified a solution that actually has multiple answers embedded within it. The constructs that look like ranges (1..2) appear to mean that the given cell could contain either 1 OR 2 and still be part of a valid solution. Of course, the selection of 1 or 2 would change the viability of the other ranges present within the same row/column.
I am not sure why the solution is coming back this way as opposed to coming back as several unique solutions.
HW2: Make the sudoku solver print prettier solutions.
For this, I went back to the original sudoku() rule and added printing.
- %-- I am the 4x4 solution.
- sudoku( Puzzle, Solution ) :-
- %-- Assert that this is only true if the Puzzle and the
- %-- Solution are the same.
- Solution = Puzzle,
-
- %-- Break the puzzle out into variables, one for each square.
- Puzzle = [
- S11, S12, S13, S14,
- S21, S22, S23, S24,
- S31, S32, S33, S34,
- S41, S42, S43, S44
- ],
-
- %-- Assert that each element within the list (which represents
- %-- the board, is in the range 1-4).
- fd_domain( Solution, 1, 4 ),
-
- %-- Define each row as a collection of cells.
- Row1 = [S11, S12, S13, S14],
- Row2 = [S21, S22, S23, S24],
- Row3 = [S31, S32, S33, S34],
- Row4 = [S41, S42, S43, S44],
-
- %-- Define each column as a collection of cells.
- Col1 = [S11, S21, S31, S41],
- Col2 = [S12, S22, S32, S42],
- Col3 = [S13, S23, S33, S43],
- Col4 = [S14, S24, S34, S44],
-
- %-- Define each square as a collection of cells.
- Square1 = [S11, S12, S21, S22],
- Square2 = [S13, S14, S34, S24],
- Square3 = [S31, S32, S41, S42],
- Square4 = [S33, S34, S43, S44],
-
- %-- Asser that all the rows, columns, and squares are valid; that
- %-- is, they contain unique values, 1-4.
- valid([
- Row1, Row2, Row3, Row4,
- Col1, Col2, Col3, Col4,
- Square1, Square2, Square3, Square4
- ]),
-
- %-- Now that all of the variables have been unified (otherwise,
- %-- we wouldn't have gotten this far), we can simply rely on the
- %-- fact that the Row variables contain valid answer. Just print
- %-- each row in its own line.
- write( '\n' ), write( Row1 ),
- write( '\n' ), write( Row2 ),
- write( '\n' ), write( Row3 ),
- write( '\n' ), write( Row4 )
- .
-
-
- %-- Empty boards are valid.
- valid( [] ).
-
- %-- The sets are valid if each set contains unique values.
- valid( Sets ) :-
- (Sets = [Head|Tail]),
- fd_all_different( Head ),
- valid( Tail )
- .
Because Prolog appears to execute its logical proofs in a short-circuited manner, we know that the end of a rule will never be reached until all the previous subgoals have been proven. Therefore, by putting the write() subgoals at the end of the rule, we know that they will only apply to solutions that have been proven.
Once the code was compiled, I was able to print 4x4 sudoku solutions:
| ?- sudoku([
_,_,2,3,
_,_,_,_,
_,_,_,_,
3,4,_,_
], Solution ).
[4,1,2,3]
[2,3,4,1]
[1,2,3,4]
[3,4,1,2]
Solution = [4,1,2,3,2,3,4,1,1,2,3,4,3,4,1,2] ? a
As you can see, it output each row (which is a list) on its own line. Then, it outputs the actual solution. There's probably a way to prevent the Solution from being output to get rid of the redundancy; but, again, my understanding of Prolog just comes up short.
Prolog does seem to be good at some things. It also appears to make many things much more difficult. I am sure that some of that is simply due to my years of thinking procedurally in programming. I'm glad that I tried Prolog; but, I'm also very glad to be moving on. This language didn't connect with me in any kind of emotional way.
Next up: Scala!
Reader Comments
You're a better man than me. I just skipped day 3.
@David,
I don't blame you. Prolog was not so cool. If I were picking a team of kick-ball players, I would definitely pick Prolog last :)
But, if you needed to schedule all the kick-ball games, along with referees, fields, and religious observations (no Sat or Sun games for some teams), etc., Prolog would be a great choice.
BTW, I am WAY behind. I got pneumonia over Christmas, and have still not fully recovered (still hacking and wheezing). I tried to read about scala, but I wrote one fairly large java program (~13 years ago), and swore I'd never do it again. I have not picked up the book in quite a while
I guess I can justify that using the JVM isn't exactly the same thing, so I should get back to it...
I was prolog programmer for more than 9 years, and my advice is that try to forget all your programming and problem solving skills before start to learn prolog, then you will be enlighted by prolog.
You probably wanted to move on, sorry to bring back bad memories...
The problem with the sudoku code in book is that it relies on a GNU Prolog extension (Finite Domain solver), but does not use it properly.
In your 6x6 version, you should add fd_labeling(Puzzle) as the last clause of sudoku6x6. It will actually compute the solution (it is not doing it right now) and replace the strange values (which are potential solutions) by the correct number.
And you're right: there's a way to make a sudoku 9x9 much simpler, and independent of the size.
Just in case, I describe my code here:
http://blog.wakatta.jp/blog/2011/10/24/seven-languages-in-seven-weeks-prolog-day-3/
I'm no more than a casual user (that is, I've used Prolog about one week over the past 15 years or so), but I guess my math background helped.
Cheers,
Frederic
I think you have a twist in Numbers there in col 2 list the value should be s23, not s32?
Excuse me again, not col 2, but square2 13, 14, 23, 24...
