4.4 Day 3: Blowing Up Vegas

You should be getting a better understanding of why I picked the Rain Man, the autistic savant, for Prolog. Though it’s sometimes difficult to understand, it’s amazing to think of programming in this way. One of my favorite points in Rain Man was when Ray’s brother realized he could count cards. Raymond and his brother went to Vegas and just about broke the bank. In this section, you’re going to see a side of Prolog that will leave you smiling. Coding the examples in this chapter was equal parts maddening and exhilarating. We’re going to solve two famous puzzles that are right in Prolog’s comfort zone, solving systems with constraints.

You may want to take a shot at some of these puzzles yourself. If you do, try describing the rules you know about each game rather than showing Prolog a step-by-step solution. We’re going to start with a small Sudoku and then give you a chance to build up to a larger one in the daily exercises. Then, we’ll move on to the classic Eight Queens puzzle.

Solving Sudoku

Coding the Sudoku was almost magical for me. A Sudoku is a grid that has rows, columns, and boxes. A typical puzzle is a nine-by-nine grid, with some spaces filled in and some blank. Each cell in the grid has a number, from 1--9 for a nine-by-nine square. Your job is to fill out the solution so that each row, column, and square has one each of all of the digits.

We’re going to start with a four-by-four Sudoku. The concepts are exactly the same, though the solutions will be shorter. Let’s start by describing the world, as we know it. Abstractly, we’ll have a board with four rows, four columns, and four squares. The table shows squares 1--4:

The first task is to decide what the query will look like. That’s simple enough. We’ll have a puzzle and a solution, of the form sudoku(Puzzle, Solution). Our users can provide a puzzle as a list, substituting underscores for unknown numbers, like this:

If a solution exists, Prolog will provide the solution. When I solved this puzzle in Ruby, I had to worry about the algorithm for solving the puzzle. With Prolog, that’s not so. I merely need to provide the rules for the game. These are the rules:

• For a solved puzzle, the numbers in the puzzle and solution should be the same.

• A Sudoku board is a grid of sixteen cells, with values from 1--4.

• The board has four rows, four columns, and four squares.

• A puzzle is valid if the elements in each row, column, and square has no repeated elements.

Let’s start at the top. The numbers in the solution and puzzle should match:

We’ve actually made some progress. Our “Sudoku solver” works for the case where there are no blanks:

The format isn’t pretty, but the intent is clear enough. We’re getting sixteen numbers back, row by row. But we are a little too greedy:

Now, this board isn’t valid, but our solver reports that there is a valid solution. Clearly, we have to limit the board to sixteen elements. We have another problem, too. The values in the cells can be anything:

For a solution to be valid, it should have numbers from 1--4. This problem will impact us in two ways. First, we may allow some invalid solutions. Second, Prolog doesn’t have enough information to test possible values for each cell. In other words, the set of results is not grounded. That means that we have not expressed rules that limit possible values of each cell, so Prolog will not be able to guess what the values are.

Let’s solve these problems by solving the next rule to the game. Rule 2 says a board has sixteen cells, with values from 1--4. GNU Prolog has a built-in predicate to express possible values, called fd_domain(List, LowerBound, UpperBound). This predicate is true if all the values in List are between LowerBound and UpperBound, inclusive. We just need to make sure all values in Puzzle range from 1 to 4.

We unified Puzzle with a list of sixteen variables, and we limited the domain of the cells to values from 1--4. Now, we fail if the puzzle is not valid:

Now, we get to the main piece of the solution. Rule 3 says a board consists of rows, columns, and squares. We’re going to carve the puzzle up into rows, columns, and squares. Now, you can see why we named the cells the way we did. It’s a straightforward process to describe the rows:

Likewise for columns:

And squares:

Now that we’ve chopped the board into pieces, we can move on to the next rule. The board is valid if all rows, columns, and squares have no repeated elements. We’ll use a GNU Prolog predicate to test for repeated elements. fd_all_different(List) succeeds if all the elements in List are different. We need to build a rule to test that all rows, columns, and squares are valid. We’ll use a simple rule to accomplish this:

This predicate is valid if all the lists in it are different. The first clause says that an empty list is valid. The second clause says that a list is valid if the first element’s items are all different and if the rest of the list is valid.

All that remains is to invoke our valid(List) rule:

Believe it or not, we’re done. This solution can solve a four-by-four Sudoku:

Breaking that into a friendlier form, we have the solution:

Here’s the completed program, beginning to end:

If you haven’t had your Prolog moment, this example should give you a nudge in the right direction. Where’s the program? Well, we didn’t write a program. We described the rules of the game: a board has sixteen cells with digits from 1--4, and none of the rows, columns, or squares should repeat any of the values. The puzzle took a few dozen lines of code to solve and no knowledge of any Sudoku solving strategies. In the daily exercises, you’ll get the chance to solve a nine-row Sudoku. It won’t be too difficult.

This puzzle is a great example of the types of problems Prolog solves well. We have a set of constraints that are easy to express but hard to solve. Let’s look at another puzzle involving highly constrained resources: the Eight Queens problem.

Eight Queens

To solve the Eight Queens problem, you put eight queens on a chess board. None can share the same row, column, or diagonal. It may appear to be a trivial problem on the surface. It’s just a kid’s game. But on another level, you can look at the rows, columns, and diagonals as constrained resources. Our industry is full of problems that solve constrained systems. Let’s look at how we can solve this one in Prolog.

First, we’ll look at what the query should look like. We can express each queen as (Row, Col), a tuple having a row and a column. A Board is a list of tuples. eight_queens(Board) succeeds if we have a valid board. Our query will look like this:

Let’s look at the goals we need to satisfy to solve the puzzle. If you want to take a shot at this game without looking at the solution, just look at these goals. I won’t show the full solution until later in the chapter.

• A board has eight queens.

• Each queen has a row from 1--8 and a column from 1--8.

• No two queens can share the same row.

• No two queens can share the same column.

• No two queens can share the same diagonal (southwest to northeast).

• No two queens can share the same diagonal (northwest to southeast).

Rows and columns must be unique, but we must be more careful with diagonals. Each queen is on two diagonals, one running from the lower left (northwest) to the upper right (southeast) and the other running from the upper left to the lower right as in Figure 5, ​Eight Queens rules​. But these rules should be relatively easy to encode.

Figure 5. Eight Queens rules

Once again, we’ll start at the top of the list. A board has eight queens. That means our list must have a size of eight. That’s easy enough to do. We can use the count predicate you saw earlier in the book, or we can simply use a built-in Prolog predicate called length. length(List, N) succeeds if List has N elements. This time, rather than show you each goal in action, I’m going to walk you through the goals we’ll need to solve the whole problem. Here’s the first goal, then:

Next, we need to make sure each queen from our list is valid. We build a rule to test whether a queen is valid:

The predicate member does just what you think; it tests for membership. A queen is valid if both the row and column are integers from 1--8. Next, we’ll build a rule to check whether the whole board is made up of valid queens:

An empty board is valid, and a board is valid if the first item is a valid queen and the rest of the board is valid.

Moving on, the next rule is that two queens can’t share the same row. To solve the next few constraints, we’re going to need a little help. We will break down the program into pieces that can help us describe the problem: what are the rows, columns, and diagonals? First up is rows. We’ll build a function called rows(Queens, Rows). This function should be true if Rows is the list of Row elements from all the queens.

This one takes a little imagination, but not much. rows for an empty list is an empty list, and rows(Queens, Rows) is Rows if the Row from the first queen in the list matches the first element of Rows and if rows of the tail of Queens is the tail of Rows. If it’s confusing to you, walk through it with a few test lists. Luckily, columns works exactly the same way, but we’re going to use columns instead of rows:

The logic works exactly the same as rows, but we match the second element of a queen tuple instead of the first.

Moving on, we’re going to number diagonals. The easiest way to number them is to do some simple subtraction and addition. If north and west are 1, we’re going to assign the diagonals that run from northwest to southeast a value of Col -- Row. This is the predicate that grabs those diagonals:

That rule worked just like rows and cols, but we had one more constraint: Diagonal is Col -- Row. Note that this is not unification! It’s an is predicate, and it will make sure that the solution is fully grounded. Finally, we’ll grab the southeast to northwest like this:

The formula is a little bit tricky, but try a few values until you’re satisfied that queens with the same sum of row and col are in fact on the same diagonal. Now that we have the rules to help us describe rows, columns, and diagonals, all that remains is to make sure rows, columns, and diagonals are all different.

So you can see it all in context, here’s the entire solution. The tests for rows and columns are the last eight clauses.

At this point, you could run the program, and it would run… and run… and run. There are just too many combinations to efficiently sort through. If you think about it, though, we know that there will be one and only queen in every row. We can jump start the solution by providing a board that looks like this:

That works just fine, but the program is still working too hard. We can eliminate the row choices quite easily and simplify the API while we’re at it. Here’s a slightly optimized version:

Philosophically, we’ve made one major change. We matched the Board with (1, _), (2, _), (3, _), (4, _), (5, _), (6, _), (7, _), (8, _) to reduce the total permutations significantly. We also removed all rules related to rows, and the results show. On my ancient MacBook, all solutions compute inside of three minutes.

Once again, the end result is quite pleasing. We built in very little knowledge of the solution set. We just described the rules to the game and applied a little logic to speed things up a little. Given the right problems, I could really find myself getting into Prolog.

What We Learned in Day 3

Today, you put together some of the ideas we’ve used in Prolog to solve some classic puzzles. The constraint-based problems have many of the same characteristics as classic industrial applications. List constraints, and crunch out a solution. We would never think of doing a SQL nine-table join imperatively, yet we don’t even blink at solving logical problems in this way.

We started with a Sudoku puzzle. Prolog’s solution was remarkably simple. We mapped sixteen variables onto rows, columns, and squares. Then, we described the rules of the game, forcing each row, column, and square to be unique. Prolog then methodically worked through the possibilities, quickly arriving at a solution. We used wildcards and variables to build an intuitive API, but we didn’t provide any help at all for solution techniques.

Next, we used Prolog to solve the Eight Queens puzzle. Once again, we encoded the rules of the game and let Prolog work into a solution. This classic problem was computationally intensive, having 92 possible solutions, but even our simple approach could solve it within a handful of minutes.

I still don’t know all of the tricks and techniques to solve advanced Sudokus, but with Prolog, I don’t need to know them. I only need the rules of the game to play.

Day 3 Self-Study

Find:

• Prolog has some input/output features as well. Find print predicates that print out variables.

• Find a way to use the print predicates to print only successful solutions. How do they work?

Do:

• Modify the Sudoku solver to work on six-by-six puzzles (squares are 3x2) and 9x9 puzzles.

• Make the Sudoku solver print prettier solutions.

If you’re a puzzle enthusiast, you can get lost in Prolog. If you want to dive deeper into the puzzles I’ve presented, Eight Queens is a good place to start.

• Solve the Eight Queens problem by taking a list of queens. Rather than a tuple, represent each queen with an integer, from 1--8. Get the row of a queen by its position in the list and the column by the value in the list.