Charlie Harvey

Prolog — Day Three

Written by Charlie on

↙

My fears of a mega hardcore third day of prolog were not realised, and I actually had some proper fun this time round. Mr. Tate is absolutely right that making a sudoku solver the prolog way is "almost magical". I’ve written sudoke solvers in perl before. And believe me it ain't pretty. With prolog you just plug in the rules, type it up and go home.

9sudoku.pl

Modify the Sudoku solver to work on […] 9x9 puzzles.

I thought that it'd be more useful to solve the actual sudoku that areout in the wild rather than a 6x6 sudoku lite. Not that it makes much difference. You just plug in more rules and extend the fd_domain. It felt a bit like cheating to reuse the code from the book. But after yesterday's brain bleeding session it was a bit of light relief.

Like I say this is just adding more columns and rows to the sudoku solver in the book. % same valid as the example in the book valid([]). valid([Head|Tail]) :- fd_all_different(Head), % predicate for no repeated elements valid(Tail). % The actual solver 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), % predicate says that values are between 1 and 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], Square1 = [S11, S12, S13, S21, S22, S23, S31, S32, S33], Square2 = [S14, S15, S16, S24, S25, S26, S34, S35, S36], Square3 = [S17, S18, S19, S27, S28, S29, S37, S38, S39], Square4 = [S41, S42, S43, S51, S52, S53, S61, S62, S63], Square5 = [S44, S45, S46, S54, S55, S56, S64, S65, S66], Square6 = [S47, S48, S49, S57, S58, S59, S67, S68, S69], Square7 = [S71, S72, S73, S81, S82, S83, S91, S92, S93], Square8 = [S74, S75, S76, S84, S85, S86, S94, S95, S96], Square9 = [S77, S78, S79, S87, S88, S89, S97, S98, S99], valid([Row1, Row2, Row3, Row4, Row5, Row6, Row7, Row8, Row9, Col1, Col2, Col3, Col4, Col5, Col6, Col7, Col8, Col9, Square1, Square2, Square3, Square4, Square5, Square6, Square7, Square8, Square9 ]).

Just a tangent from Prolog for a moment. This might have involved much boring typing, but I’d rather spend twice as long figuring out a way to not type something that Vim could type for me. In this case it didn't even take too long to work out. Here are some quick regexps that turned out useful for me.

  • Rows: Delete Row2 and on. Then add extra columns to Row1. Next visual select Row1 and yank (or just yy). Then paste 8 times below Row1. Then do :s/w1/w2/ :s/S1/S2/g for the rest of the Rows, substituting 2 for the correct row number.
  • Cols: Same sketch with deleting all the other columns completing the extras for Col1 and now do this on each line :s/S\(\d\)1/S\12/g , again substituting 2 for the right Col number.
  • Squares: This time I completed the first three squares, then yanked and pasted twice and ran :'<,'>s/S1/S4/g :'<,'>s/S2/S5/g :'<,'>s/S3/S6/g , the second time 4,5,6 became 7,8,9.

OK, going back to the regularly scheduled programme, this was blitteringly fast and solved my painstakingly typed in test sudoku with ease. I did look at extending the solver to take input from a file or something but I figure that is for another day. | ?- sudoku([ 3, 6, _, _, 7, 1, 2, _, _, _, 5, _, _, _, _, 1, 8, _, _, _, 9, 2, _, 4, 7, _, _, _, _, _, _, 1, 3, _, 2, 8, 4, _, _, 5, _, 2, _, _, 9, 2, 7, _, 4, 6, _, _, _, _, _, _, 5, 3, _, 8, 9, _, _, _, 8, 3, _, _, _, _, 6, _, _, _, 7, 6, 9, _, _, 4, 3 ] , Solution ). Solution = [3,6,4,8,7,1,2,9,5,7,5,2,9,3,6,1,8,4,8,1,9,2,5,4,7,3,6,5,9,6,7,1,3,4,2,8,4,3,1,5,8,2,6,7,9,2,7,8,4,6,9,3,5,1,6,4,5,3,2,8,9,1,7,9,8,3,1,4,7,5,6,2,1,2,7,6,9,5,8,4,3] That is correct by the way. This fact blew my mind. It did seem magical.

pretty9sudoku.pl

Make the Sudoku Solver print prettier solutions.

It took me a while to research this. It turns out that gprolog doesn't have writef. But it also turns out that format does the same sort of thing. It tooke me a while to grok the manual though. Anyhow, I rether like the format used by Peter Norvig, over on his solving every sudoku page. So, I made it do that. I guess I should have called my say function writeln. But say is my cheeky nod to Perl. % Save some typing later on. This is like say in Perl 5.10 or writeln in pascal say(Arg) :- write(Arg), nl. % took me a while to figure out that format formatted and wrote, a-la printf % print a row with some seperators sayRow(Arg) :- format(' %d %d %d | %d %d %d | %d %d %d ',Arg), nl. % print a seperator row saySep(_) :- say('---------+---------+---------'). % same valid as the example in the book valid([]). valid([Head|Tail]) :- fd_all_different(Head), % predicate for no repeated elements valid(Tail). % The actual solver 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), % predicate says that values are between 1 and 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], Square1 = [S11, S12, S13, S21, S22, S23, S31, S32, S33], Square2 = [S14, S15, S16, S24, S25, S26, S34, S35, S36], Square3 = [S17, S18, S19, S27, S28, S29, S37, S38, S39], Square4 = [S41, S42, S43, S51, S52, S53, S61, S62, S63], Square5 = [S44, S45, S46, S54, S55, S56, S64, S65, S66], Square6 = [S47, S48, S49, S57, S58, S59, S67, S68, S69], Square7 = [S71, S72, S73, S81, S82, S83, S91, S92, S93], Square8 = [S74, S75, S76, S84, S85, S86, S94, S95, S96], Square9 = [S77, S78, S79, S87, S88, S89, S97, S98, S99], valid([Row1, Row2, Row3, Row4, Row5, Row6, Row7, Row8, Row9, Col1, Col2, Col3, Col4, Col5, Col6, Col7, Col8, Col9, Square1, Square2, Square3, Square4, Square5, Square6, Square7, Square8, Square9 ]), % At this point we must be valid, so we'll print out the Rows. sayRow(Row1), sayRow(Row2), sayRow(Row3), saySep(_), sayRow(Row4), sayRow(Row5), sayRow(Row6), saySep(_), sayRow(Row7), sayRow(Row8), sayRow(Row9), nl, nl . Now when we consult and run the code on the same Sudoku we get this. | ?- sudoku([ 3, 6, _, _, 7, 1, 2, _, _, _, 5, _, _, _, _, 1, 8, _, _, _, 9, 2, _, 4, 7, _, _, _, _, _, _, 1, 3, _, 2, 8, 4, _, _, 5, _, 2, _, _, 9, 2, 7, _, 4, 6, _, _, _, _, _, _, 5, 3, _, 8, 9, _, _, _, 8, 3, _, _, _, _, 6, _, _, _, 7, 6, 9, _, _, 4, 3 ] , Solution ). 3 6 4 | 8 7 1 | 2 9 5 7 5 2 | 9 3 6 | 1 8 4 8 1 9 | 2 5 4 | 7 3 6 ---------+---------+--------- 5 9 6 | 7 1 3 | 4 2 8 4 3 1 | 5 8 2 | 6 7 9 2 7 8 | 4 6 9 | 3 5 1 ---------+---------+--------- 6 4 5 | 3 2 8 | 9 1 7 9 8 3 | 1 4 7 | 5 6 2 1 2 7 | 6 9 5 | 8 4 3 Solution = [3,6,4,8,7,1,2,9,5,7,5,2,9,3,6,1,8,4,8,1,9,2,5,4,7,3,6,5,9,6,7,1,3,4,2,8,4,3,1,5,8,2,6,7,9,2,7,8,4,6,9,3,5,1,6,4,5,3,2,8,9,1,7,9,8,3,1,4,7,5,6,2,1,2,7,6,9,5,8,4,3] I’ve not been able to find a way of suppressing the "Solution = […]" line. Let me know in the comments how I should do that!

Some thoughts on Prolog

My suspicion is that Prolog is one of those languages like Lisp which has an almost zenlike quality when you finally get it. I think that there were a few glimpses of this. I’m sort of inspired. It has been a while since I struggled cnceptually rather than syntactically with a language, perhaps the last time being when I was working my way through Higher Order Perl.I might get hold of a Prolog book and learn a little more about the language. Its clear that there are some things that it makes rather easy that I might struggle with in other languages. Well, my next language is to be Scala, should be an interesting one.


Comments

  • Be respectful. You may want to read the comment guidelines before posting.
  • You can use Markdown syntax to format your comments. You can only use level 5 and 6 headings.
  • You can add class="your language" to code blocks to help highlight.js highlight them correctly.

Privacy note: This form will forward your IP address, user agent and referrer to the Akismet, StopForumSpam and Botscout spam filtering services. I don’t log these details. Those services will. I do log everything you type into the form. Full privacy statement.