Eight queens puzzle (J)
From LiteratePrograms
The eight queens problem is the problem of placing eight queens on an 8×8 chessboard such that none of them attack one another (no two are in the same row, column, or diagonal). More generally, the n queens problem places n queens on an n×n chessboard.
Contents |
theory
The eight queens puzzle follows the hylomorphic pattern commonly known as "generate and test" — we first unfold a set of possible solutions, and then fold over them, retaining only the ones without captures.
In theory, the following one-line expression suffices to solve the puzzle
(#~[:(0=>./)[:,/[:([:}.([:i.#)=[:|(]-"1{.))\.|:)(i.A.~[:i.!) 8
but in practice, we prefer to articulate the program.
practice
Our top level expression follows the generate and test paradigm:
<<8 queens>>= (where good) sols 8
- sols 8 generates a set of possible solutions for an 8x8 board
- good tests for actual solutions, satisfying the given constraints
generation
A little thought suffices to show that any solution must have one queen in each column, so we can represent each possible board position by listing the rows in which each queen is placed. Furthermore, there must also be only one queen in each row, so we can start by generating all the permutations of 8 rows.
- i.y generates the basic ordering, "0 1 2 3 4 5 6 7" — all queens along the diagonal
- i.!y generates the indices (i.) of the y! possible permutations
- A., or Anagram, then generates the set of the y! permutations of the basic position.
<<definitions>>= sols=: monad : '(i.!y) A. (i.y)'
attention!
Note that monad here only refers to the fact that we are defining a function that takes one argument, called y — as opposed to a dyadic function such as A. that takes both left and right arguments (which would be written in a definition as x and y respectively). In the sequel we continue to define functions using this construct.
Question: which Haskell-style monads are present in this program? Can you find List, Maybe, and the MaxPlus monoid?
testing
The good positions, the solutions of the puzzle, are those where no captures are possible:
<<definitions>>= good=: monad : 'zero caps y'
We have, by design, eliminated horizontal and vertical captures, so we need only test for the existence of diagonal captures. Again, this is divided into a generating anamorphism and a testing catamorphism.
- (diag\.) unfolds each board position into a series of tests for diagonal alignment between the queen in each column and those in the following columns
- (,/) then refolds the results, concatenating them into a single list (which zero will then fold down to a single boolean indicating the validity of the board position)
<<definitions>>= caps=: monad : ',/diag\. |:y'
(the initial transposition (|:) is an isomorphism — it's incidental to the theoretical process, but important in practice)
Two queens are on the same diagonal when their distance in rows (| diff, where | is the absolute value) is the same as (=) their distance in columns, generated here by counting up (i.) to the number of columns (#y). A queen is always diagonally coincident with itself, so we apply behead (}.) to remove the first result, eliminating this reflexive case.
<<definitions>>= diag=: monad : '}. (i. #y)=(| diff y)'
Finding the difference in rows is simply a matter of subtracting out the position of the piece in the first column ({.y), thereby converting a list of absolute to a list of relative row positions.
<<definitions>>= diff=: monad : 'y -"1 {.y'
The modified rank (-"1) for the subtraction, in conjunction with the earlier transposition, is a technical detail which allows us to calculate the captures for all boards breadthwise, in parallel.
wrapping up
We must provide two more small definitions:
- zero tests that the maximum of a list (>./) is equal to 0.
- where is the passive form of repeat (#) — a repeat with a boolean argument is a simply a projection, and by using the passive adverb (~) we are able to arrange that the right argument projects elements from the left, rather than vice versa.
These definitions are simple enough that we write them directly, in point-free style.
<<ancillary defs>>= where=: #~ zero=: 0=>./
When we say (where good) sols 8, we take advantage of one of
J's unusual syntactic constructs.
The pair of functions where and good
is treated as a fork —
the argument is shared, resulting in an expression
which might be expressed in a different syntax
as "let v = sols 8 in v `where` (good v)".
Question: what are the parallels between the phrase (where good) sols 8 and a list comprehension?
Finally, we add some boilerplate to make a small script
<<8queens.ijs>>= ancillary defs definitions echo 8 queens exit ''
that prints the expected 92 solutions, of which the first few (those with a queen at the origin) are:
0 4 7 5 2 6 1 3 0 5 7 2 6 3 1 4 0 6 3 5 7 1 4 2 0 6 4 7 1 3 5 2 ...
Exercise: produce only the 12 unique solutions by eliminating symmetric duplicates
Exercise: add a command line argument to specify the board size
| Download code |