Chess

Solving a chess puzzle with Claude and Prolog

Posted on by John

Prolog is the original logic programming language. The name comes from programming in logic. More specifically, the name comes from programmation en logique because the inventor of the language, Philippe Roussel, is French.

Prolog has its advantages and disadvantages. One of the advantages is that the language represents logical problems directly. One of the disadvantages is that the syntax can be quirky. But if an LLM is writing the code, or at least helping to write the code, the syntax doesn’t matter so much.

I wanted to see how well Claude (Sonnet 4.6, medium effort) could solve a chess puzzle by Martin Gardner that I wrote about a little over a year ago. I chose a relatively obscure problem rather than something like the Eight Queens puzzle because an LLM could simply quote one of countless articles on the puzzle.

The puzzle

As I stated in the post last year, the task is to place two rooks, two bishops, and two knights on a 4 by 4 chessboard so that no piece attacks any other.

There are two basic solutions, twelve if you count rotations and reflections as different solutions.

Prolog results

Claude wrote an SWI-Prolog program that I ran with

swipl -g "run, halt" chess_placement.pl

and it gave the following output.

Total solutions (raw): 12
Solutions up to D4 symmetry: 2
Solutions up to D4 symmetry: 2

Solution 1:
B . . N
N . . B
. R . .
. . R .

Solution 2:
. B N .
. . . R
R . . .
. N B .

Claude made a nice image of the solutions.

Note that you can make eight variations of the first solution by a combination of rotations and flips. There are only four variations of the second solution because two rotations put you back where you started.

Prolog source

Here’s the Prolog code that Claude generated.

% ============================================================
%  Non-attacking placement of 2 Rooks, 2 Bishops, 2 Knights
%  on a 4x4 chessboard
%
%  Run with SWI-Prolog:
%    swipl -g "run, halt" chess_placement.pl
%
%  Or interactively:
%    swipl chess_placement.pl
%    ?- run.
%    ?- count_solutions(N).
%    ?- count_unique(N).
% ============================================================

:- use_module(library(lists)).

% ---- Board squares: (Row, Col) with Row, Col in 0..3 ----------------

square(R, C) :- member(R, [0,1,2,3]), member(C, [0,1,2,3]).

% ---- Attack predicates ----------------------------------------------

rook_attacks(R,_,R,_).          % same row
rook_attacks(_,C,_,C).          % same column

bishop_attacks(R1,C1,R2,C2) :-
    DR is abs(R1-R2), DC is abs(C1-C2),
    DR =:= DC, DR > 0.

knight_attacks(R1,C1,R2,C2) :-
    DR is abs(R1-R2), DC is abs(C1-C2),
    ( DR =:= 1, DC =:= 2 ; DR =:= 2, DC =:= 1 ).

% attacks(+Type1, +R1, +C1, +Type2, +R2, +C2)
% True if either piece threatens the other's square.
attacks(rook,   R1,C1, _,     R2,C2) :- rook_attacks(R1,C1,R2,C2).
attacks(_,      R1,C1, rook,  R2,C2) :- rook_attacks(R1,C1,R2,C2).
attacks(bishop, R1,C1, _,     R2,C2) :- bishop_attacks(R1,C1,R2,C2).
attacks(_,      R1,C1, bishop,R2,C2) :- bishop_attacks(R1,C1,R2,C2).
attacks(knight, R1,C1, _,     R2,C2) :- knight_attacks(R1,C1,R2,C2).
attacks(_,      R1,C1, knight,R2,C2) :- knight_attacks(R1,C1,R2,C2).

% ---- All pairs safe -------------------------------------------------

% Check all unordered pairs in a list.
no_attack_pair(_, []).
no_attack_pair(T1-(R1,C1), [T2-(R2,C2)|Rest]) :-
    \+ attacks(T1,R1,C1,T2,R2,C2),
    no_attack_pair(T1-(R1,C1), Rest).

all_pairs_safe([]).
all_pairs_safe([P|Rest]) :-
    no_attack_pair(P, Rest),
    all_pairs_safe(Rest).

% ---- Generate a placement -------------------------------------------
%
%  Placement = [rook-(R1,C1), rook-(R2,C2),
%               bishop-(R3,C3), bishop-(R4,C4),
%               knight-(R5,C5), knight-(R6,C6)]
%
%  We enforce an ordering within each pair to avoid counting
%  same-type duplicates (rook1 vs rook2 swapped).
%  Squares are represented canonically: (R,C) with R*4+C as index.

sq_index(R, C, I) :- I is R*4 + C.

placement(Placement) :-
    % --- Rooks ---
    square(R1r, C1r), square(R2r, C2r),
    sq_index(R1r,C1r,I1r), sq_index(R2r,C2r,I2r),
    I1r < I2r,          % canonical order for the two rooks

    % --- Bishops ---
    square(R1b, C1b), square(R2b, C2b),
    sq_index(R1b,C1b,I1b), sq_index(R2b,C2b,I2b),
    I1b < I2b,          % canonical order for the two bishops

    % --- Knights ---
    square(R1n, C1n), square(R2n, C2n),
    sq_index(R1n,C1n,I1n), sq_index(R2n,C2n,I2n),
    I1n < I2n,          % canonical order for the two knights

    % --- All six squares distinct ---
    Squares = [(R1r,C1r),(R2r,C2r),(R1b,C1b),(R2b,C2b),(R1n,C1n),(R2n,C2n)],
    all_distinct_squares(Squares),

    % --- Build placement list ---
    Placement = [ rook-(R1r,C1r),   rook-(R2r,C2r),
                  bishop-(R1b,C1b), bishop-(R2b,C2b),
                  knight-(R1n,C1n), knight-(R2n,C2n) ],

    % --- No piece attacks any other ---
    all_pairs_safe(Placement).

all_distinct_squares([]).
all_distinct_squares([S|Rest]) :-
    \+ member(S, Rest),
    all_distinct_squares(Rest).

% ---- Count all solutions --------------------------------------------

count_solutions(N) :-
    findall(P, placement(P), Ps),
    length(Ps, N),
    format("Total solutions (raw): ~w~n", [N]).

% ---- D4 symmetry transformations on a 4x4 board ---------------------
%  Squares (R,C) in 0..3

transform(identity, R, C, R,  C).
transform(rot90,    R, C, C,  Nr) :- Nr is 3-R.
transform(rot180,   R, C, Nr, Nc) :- Nr is 3-R, Nc is 3-C.
transform(rot270,   R, C, Nc, R)  :- Nc is 3-C.
transform(flipH,    R, C, R,  Nc) :- Nc is 3-C.
transform(flipV,    R, C, Nr, C)  :- Nr is 3-R.
transform(flipD1,   R, C, C,  R).
transform(flipD2,   R, C, Nr, Nc) :- Nr is 3-C, Nc is 3-R.

apply_transform(_, [], []).
apply_transform(T, [Type-(R,C)|Rest], [Type-(NR,NC)|TRest]) :-
    transform(T, R, C, NR, NC),
    apply_transform(T, Rest, TRest).

% Canonical form: sort pieces within same-type pairs, then sort the
% whole list to get a unique representative.
canonical_placement(Placement, Canonical) :-
    findall(T, member(T,[identity,rot90,rot180,rot270,
                          flipH,flipV,flipD1,flipD2]), Ts),
    maplist(transform_and_sort(Placement), Ts, AllForms),
    msort(AllForms, Sorted),
    Sorted = [Canonical|_].

transform_and_sort(Placement, T, Sorted) :-
    apply_transform(T, Placement, TPl),
    msort(TPl, Sorted).

% ---- Count solutions up to D4 symmetry ------------------------------

count_unique(N) :-
    findall(P, placement(P), Ps),
    maplist(canonical_placement, Ps, Canonicals),
    list_to_set(Canonicals, Unique),
    length(Unique, N),
    format("Solutions up to D4 symmetry: ~w~n", [N]).

% ---- Pretty-print a board -------------------------------------------

print_board(Placement) :-
    forall(member(R, [0,1,2,3]),
           print_row(R, Placement)),
    nl.

print_row(R, Placement) :-
    forall(member(C, [0,1,2,3]),
           print_cell(R, C, Placement)),
    nl.

print_cell(R, C, Placement) :-
    (   member(rook-(R,C),   Placement) -> write('R ')
    ;   member(bishop-(R,C), Placement) -> write('B ')
    ;   member(knight-(R,C), Placement) -> write('N ')
    ;   write('. ')
    ).

% ---- Print all unique solutions -------------------------------------

print_unique_solutions :-
    findall(P, placement(P), Ps),
    maplist(canonical_placement, Ps, Canonicals),
    list_to_set(Canonicals, Unique),
    length(Unique, N),
    format("~nSolutions up to D4 symmetry: ~w~n~n", [N]),
    forall(nth1(I, Unique, Sol),
           ( format("Solution ~w:~n", [I]),
             print_board(Sol) )).

% ---- Top-level entry point ------------------------------------------

run :-
    count_solutions(Raw),
    count_unique(Sym),
    format("~n"),
    print_unique_solutions,
    format("Summary: ~w raw solutions, ~w up to D4 symmetry.~n",
           [Raw, Sym]).

Knight’s tour with fewest obtuse angles

Posted on by John

Donald Knuth gives a public lecture each year around Christmas. This year was his 29th Christmas lecture, Adventures with Knight’s Tours.

I reproduced one of the images from his lecture.

Knight's tour with the minimum number of obtuse angles

This is the knight’s tour with the minimum number of obtuse angles, marked with red dots. The solution is unique, up to rotations and reflections.

Knuth said he thought this was one of the most beautiful knight’s tours. He discusses this tour about 44 minutes into the video here.

More knight’s tour posts

An uncrossed knight’s tour

Posted on by John

I’ve written several times about knight’s tours of a chessboard. The paths in these tours cross each other many times. What if you wanted to look tours that do not cross themselves? You can’t reach every square this way. You can reach half of them, but no more than half.

The following tour is part of the article Uncrossed Knight’s Tours in Donald Knuth’s book Selected Papers on Fun & Games.

Related posts

Trinomial Coefficients and Kings

Posted on by John

The term trinomial coefficient is used a couple different ways. The most natural use of the term is a generalization of bionomial coefficients to three variables, i.e. numbers of the form

\frac{n!}{i! \, j! \, k!}

where i + j + k = n. These numbers are the coefficients of yj zk in the expansion of (x + y + z)n.

But there’s another use of the term trinomial coefficient, the one that we are interest in for this post, and that is the coefficients of xk in the expansion of (1 + x + 1/x)n. These numbers can be visualized in a triangle analogous to Pascal’s triangle.

In Pascal’s triangle, each entry is the sum of the two entries above it. In the trinomial triangle, each entry is the sum of the three entries above it.

If you’ve been reading this blog regularly you know I’ve been interested in chess puzzles lately. The thing that make me interested in trinomial coefficients is that they relate to moves of a king on a chessboard.

If you note the number paths a king can take to a square using the minimal number of moves, you get the trinomial triangle. The reason is simple: the number of ways to get to a square equals the number of ways to get there via the square up and to the left, plus the number of ways to get their via the square above, plus the number of ways to get their via the square up and to the right.

Related posts

Another little chess puzzle

Posted on by John

Here’s another little chess puzzle by Martin Gardner, taken from the same paper as earlier.

The task is to place two rooks, two bishops, and two knights on a 4 by 4 chessboard so that no piece attacks any other.

As before, there are two basic solutions, plus symmetries.

See this post for solutions, and a Prolog program that finds and enumerates the solutions.

A crowded little chess puzzle

Posted on by John

Here’s a puzzle by Martin Gardner [1].

Can a queen, king, rook, bishop, and knight be placed on a 4² board so no piece attacks another?

There are two solutions, plus symmetries.

Note that in all non-attacking chess puzzles, the colors of the pieces are irrelevant. In the solutions I chose the piece colors to be the opposite of the square colors strictly for aesthetic reasons.

More chess posts

More Martin Gardner posts

[1] Martin Gardner. Some New Results on Nonattacking Chess Tasks. Math Horizons. February 2001, pp 10–12.

Special solutions to the eight queens problem

Posted on by John

There are 92 ways to place eight queens on a chessboard so that no queen is attacking any other. These fall into 12 equivalence classes. The 92 solutions are all rotations and reflections of these 12 basic solutions.

If you think about the previous numbers a minute, you might wonder why the total number of solutions is not a multiple of 12. There is one particular solution that is more symmetric than the others. So the total number of solutions 92 breaks down into

8 × 11 + 4 × 1.

To illustrate this, let’s look at two fundamental solutions: one that is particularly ordered and one that is particularly disordered in a sense that we’ll get to later on.

Most basic solutions, like the one below, are part of an equivalence class of eight solutions.

You can rotate the board 90° or reflect it about the middle[1], or some combination of both [2]. This amounts to eight possibilities.

This solution, however, is more symmetric.

You can rotate the basic solution, but flipping it over does not create a new solution: a flip produces the same result as two 90° rotations.

It’s curious that there is only one highly symmetric solution to the eight queens problem. When I first saw the problem as a child I expected all the solutions to be highly symmetric. That may be why I wasn’t able to find a solution.

Among the 11 basic solutions that are less ordered, the one shown above is uniquely disordered in the following sense: no three queens lie on a straight line.

The eight queens problem is a problem about restricted straight lines. It says no two queens lie on the same rank, file, or diagonal. But if we look at all straight lines, then of course there is a line through any two queens. In the most orderly solution, every queen is on a straight line with two others. In the least orderly solution, no queen is on a straight line with two others.

In 1900 Henry Dudenay introduced the no-three-in-line problem, looking at ways to place points on a lattice such that no line goes through three points, with no restriction on the slope of the lines. So one family of solutions to the eight queens problem is also a solution to the no-three-in-line problem.

Related posts

[1] It doesn’t matter whether you flip about the horizontal or vertical axis.

[2] In fancy terminology, the action of the dihedral group D8 applied to a solution yields another solution.

The non-attacking bishops problem

Posted on by John

How many bishops can you place on a chessboard so that no bishop is attacking any other bishop?

For a standard 8 × 8 chessboard the answer is 14. In general, for an n × n chessboard the answer is 2n − 2.

Here’s one way to place the maximum number of non-attacking bishops.

To see that the bishops cannot attack each other, I think it’s helpful to imagine extending the chessboard so that each bishop attacks the same number of squares. Then we can see that they miss each other.

Related posts

n-queens in 3D

Posted on by John

It’s possible to place n queens on an n × n chess board so that no queen is attacking any other queen, provided n > 3. A queen is able to move any number of squares in any horizontal, vertical, or diagonal direction. Another way to put it is that the queen can move in any of 8 = 3² − 1 directions, in the direction of any cell in a 3 × 3 grid centered on the queen.

What if we extend chess to three dimensions? Now we have an n × n × n cube. Now a queen is able to move in 26 = 3³ − 1 directions, in the direction of any cell in a 3 × 3 × 3 cube centered on the queen.

Klarner [1] proved that it is possible to place n² queens in an n × n × n cube so that no queen is attacking any other, provided gcd(n, 210) = 1, i.e. provided the smallest prime factor of n is larger than 7. The condition gcd(n, 210) = 1 is sufficient, and it is conjectured to be necessary as well [2].

Klarner constructed a solution as follows: Place the queens on

(i, j, (3i + 5j) mod n)

for i and j running from 1 to n.

One way to visualize the queens in 3D is to draw a 2D grid where each cell contains the vertical coordinate of the corresponding queen. This grid will be a Latin square, and so the 3D queen placement problem is also known as the Latin queen problem.

Here’s a visualization of Klarner’s example.

Note that if you only pay attention to a particular number, you have a solution to the 11 queens problem in a square. That’s because every slice of a 3D solution is a solution to the 2D problem.

I played around with plotting the points in three dimensions. Here’s one view.

A slight rotation of the cube gives a substantially different perspective. This would be better as an animation, available here.

Mathematica code

Here’s the code that made the images above.

Flat grid:

    Grid[
        Table[
            Mod[3 i + 5 j, 11], 
            {i, 0, 10}, 
            {j, 0, 10}
        ], 
        Frame -> All
    ]

Static 3D view:

     ListPointPlot3D[
         Table[
             {i, j, Mod[3 i + 5 j, 11]}, 
             {i, 0, 10}, 
             {j, 0, 10}
          ], 
          BoxRatios -> {1, 1, 1}, 
          PlotStyle -> {PointSize[0.02]}
      ]

Animation:

    Animate[
        ListPointPlot3D[
            Table[
                {i, j, Mod[3 i + 5 j, 11]}, 
                {i, 0, 10}, 
                {j, 0, 10}
            ], 
        BoxRatios -> {1, 1, 1}, 
        PlotStyle -> {PointSize[0.02]}, 
        ViewPoint -> {2 Cos[t], 2 Sin[t], 1}
        ], 
        {t, 0, Pi, 0.05}, 
        AnimationRunning -> True, 
        AnimationRate -> 4
    ]

    Export["klerner_animation.gif", %]

Related posts

[1] D.A. Klarner, Queen squares, J. Recreational Math. 12 (3) (1979/1980) 177–178.

[2] Jordan Bell and Brett Stevens. A survey of known results and research areas for n-queens. Discrete Mathematics 309 (2009) 1–31