# Seven Languages In Seven Weeks: Prolog - Day 3

Posted December 10, 2010 at 10:00 AM by Ben Nadel

Tags: Prolog

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!

### Looking For a New Job?

25% of job board revenue is donated to Kiva. Loans that change lives - Find out more »

Dec 11, 2010 at 2:37 AM // reply »

You're a better man than me. I just skipped day 3.

Dec 15, 2010 at 10:19 AM // reply »

@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 :)

Jan 18, 2011 at 11:27 AM // reply »

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...

Sep 25, 2011 at 5:38 AM // reply »

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.

Oct 24, 2011 at 10:19 AM // reply »

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

Jan 30, 2013 at 2:57 AM // reply »

I think you have a twist in Numbers there in col 2 list the value should be s23, not s32?

Jan 30, 2013 at 3:01 AM // reply »

Excuse me again, not col 2, but square2 13, 14, 23, 24...

Comment Etiquette: Please do not post spam. Please keep the comments on-topic. Please do not post unrelated questions or large chunks of code. And, above all, please be nice to each other - we're trying to have a good conversation here.

Please review the following issues:

 Author Name: Author Email: Author Website: Comment: Supported HTML tags for formatting: bold   italic   code Remember my information Subscribe to comments Send me a copy of this comment
InVision App - Prototyping Made Beautiful With Prototyping Tools Recent Blog Comments
Mar 11, 2014 at 6:20 PM
Reading In File Data One Line At A Time Using ColdFusion's CFLoop Tag Or Java's LineNumberReader
Thanks Ben for you very interesting articles on handling large files. As I am not a programmer, I am quite insecure whether my issue is directly related to your description or not. My problem is, tha ... read »
Mar 11, 2014 at 12:21 PM
Compound Transclusion Prevented In AngularJS 1.2
Yeah this hit our team too and locked us as 1.1.5. It seemed like an irresponsible unilateral decision, but our graver concern is the future decisions the Angular team will make with other fundamenta ... read »
Mar 11, 2014 at 2:00 AM
ColdFusion, jQuery, And "AJAX" File Upload Demo
hey Ben Nadel thanks for this tutorial. i have downloaded your code also but no luck.. i am new to this so , can you explain me some thing about this cf prefix ? ... read »
Mar 10, 2014 at 8:24 PM
Nested Views, Routing, And Deep Linking With AngularJS
@Steven, the action property is not something from AngularJS but rather part of the concept that Ben is describing in his blogpost here. it is a custom added property, which is read by the requestCo ... read »
Mar 10, 2014 at 2:03 PM
Nested Views, Routing, And Deep Linking With AngularJS
Where is the angular documentation for 'action:' it is not here: http://docs.angularjs.org/api/ngRoute/provider/ \$routeProvider Thanks. ... read »
Mar 10, 2014 at 12:06 PM
Using Track-By With ngRepeat In AngularJS 1.2
I was hoping that this will work with pagination using ng-repeat. My use case scenario is that I have an images object. images[0] = [im1,im2,im3] // First Page images[1] = [im4, im5, im6] // Second ... read »
Mar 9, 2014 at 6:11 PM
For Better Security Use HtmlEditFormat() In Conjunction With JSStringFormat() In ColdFusion
It looks like htmleditformat() will be deprecated in CF 11 https://wikidocs.adobe.com/wiki/display/coldfusionen/New +in+ColdFusion ... read »
Mar 9, 2014 at 10:55 AM
\$.stop() vs. \$.finish() In jQuery Animations
Nice feature! Thanks for sharing. :) Good for when you are making a 100% AJAX controlled site. ... read »