Cheating Linguists

Constrained Permutations in Prolog

Problem posted to comp.lang.prolog by Daniel Dudley

Problem Statement

A university was to hold an examination in 5 subjects: Norwegian, German, English, French and Spanish. In each of these languages there were 4 candidates. The examination room was therefore divided into 20 cells, as shown in the figure below (view this in a fixed font):

figure( [
" X    ",
" XXXXX",
" XXXX ",
" XXXX ",
"XXXXX ",
"    X "
] ).

The university's administration wanted to secure themselves against cheating. Candidates in the same language were to be completely isolated from each other - so much so that their cells were not to coincide even at the corners.

A young lecturer was given the job of finding a solution to the problem, which he did, and justly received a pat on the back from the dean.

Now it just so happens that the dean is an ardent prolog programmer in his spare time (how else could he make dean?) and, realizing that there could be several solutions to the problem, used his skills to find all solutions. Can you do the same?

Note

“Several solutions” doesn't really cover it! Assuming that by ‘a solution’ we mean finding a mapping between candidates and cells, then, having found one such solution, we can easily find 955,514,879 other members of its solution “family” through:

• candidate permutation: There are (4!)⁵ permutations of the candidates within the cells allocated to their subjects;
• subject permutation: we can multiply the candidate permutations by the 5! permutations of the subjects allocated to particular sets of cells.

This means that the total number of solutions is 955514880 × D where D is the number of solution families i.e. solutions that cannot be derived from each other by candidate or subject permutation.

Finding D is the more interesting problem solved by this program.

nut1( ?Solutions )

Solutions is the number of distinct solutions to the subject/cell allocation problem for any five different subjects.

nut1( Solutions ) :-
    Norwegian = 1,
    German    = 2,
    English   = 3,
    French    = 4,
    Spanish   = 5,
    candidates( [Norwegian,German,English,French,Spanish], Candidates ),
    cells( Cells ),
    count_solutions( allocate(Cells,Candidates), Solutions ).

allocate( +Cells, +Candidates )

holds when each cell in Cells holds a candidate from Candidates.

allocate( Cells, Candidates ) :-
    allocation( Cells, 1, Candidates ).

allocation( +Cells, +NextSubject, +Subjects )

holds when Cells is a representation of a distinct solution to the subject/cell allocation problem. NextSubject is the highest subject that can be allocated next, while Subjects is the list of subjects needing allocation to Cells.

Each subject is represented by a list, in which each occurrence of the subject number represents a candidate.

We guarantee distinct solutions by ensuring that the allocation is made on the following basis:

• For each subject: the location of the N+1th candidate must be a successor of the location of the Nth candidate - to eliminate candidate permutations.
• The location of the first candidate of the N+1th subject must be a successor of the location of the first candidate of the Nth subject – to eliminate subject permutations.

Operationally, at each step we select a candidate for a cell and constrain each of the cell's adjacent successors to have a different subject from it.

allocation( [], _Next, [] ).
allocation( [Cell|Cells], Next, Subjects ) :-
    allocate_candidate( Subjects, Next, Candidate, Subjects1, Next1 ),
    cell( Candidate, Cell ),
    adjacent_successors( Cell, AdjacentSuccessors ),
    blocked( AdjacentSuccessors, Candidate ),
    allocation( Cells, Next1, Subjects1 ).

allocate_candidate( +Subjects, +Next, ?Candidate, ?Subjects1, ?Next1 )

holds when Candidate is taken from Subjects leaving Subjects1. Candidate is represented by a subject number ≤ Next. Next1 is the highest subject that can be allocated to the next cell, ensuring that the first candidate for each subject is allocated in order.

allocate_candidate( [Subject|Subjects], Next, Candidate, Subjects1, Next1 ) :-
    Subject = [Candidate|Candidates],
    Candidate =< Next,
    Next1 is max(Candidate+1,Next),
    residual_candidates( Candidates, Subjects, Subjects1 ).
allocate_candidate( [Subject|Subjects], Next, Candidate, [Subject|Subjects1], Next1 ) :-
    Subject = [Candidate0|_Candidates],
    Candidate0 < Next,
    allocate_candidate( Subjects, Next, Candidate, Subjects1, Next1 ).

residual_candidates( [], Subjects, Subjects ).
residual_candidates( Candidates, Subjects, [Candidates|Subjects] ) :-
    Candidates = [_|_].

cells( ?Layout )

holds when Layout is a list of cells ordered by their row × column coordinates.

Each cell is described by 5 binary digits, which indicate the subject assigned to it, and the set of successors of the cell that are adjacent to it.

cells( Layout ) :-
    findall( location_cell(Row,Column,_Cell), location(Row, Column), Cells ),
    sort( Cells, Ordered ),
    cells1( Ordered, Layout ).

cells1( [], [] ).
cells1( [location_cell(Row,Column,Cell)|Successors], [Cell|Matrix] ) :-
    adjacent_successors( Cell, AdjacentSuccessors ),
    cells2( Successors, Row, Column, AdjacentSuccessors ),
    cells1( Successors, Matrix ).

cells2( [], _Row, _Column, [] ).
cells2( [location_cell(Row1,Column1,Cell)|Layout], Row, Column, Adjacent ) :-
    ( adjacent( Row, Row1 ),
      adjacent( Column, Column1 ) ->
        Adjacent = [Cell|Adjacent1]
    ; otherwise ->
        Adjacent = Adjacent1
    ),
    cells2( Layout, Row, Column, Adjacent1 ).

location( ?Row, ?Column )

holds when Row and Column are the (unary) row and column offsets of an "X" in figure/1.

location( Row, Column ) :-
    X is "X",
    figure( Drawing ),
    offset( Cells, Drawing, Row ),
    offset( X, Cells, Column ).

cell( ?Subject, ?Cell )

holds when Cell is the cell representation for Subject.

cell( 1, cell(1,0,0,0,0,_) ).
cell( 2, cell(0,1,0,0,0,_) ).
cell( 3, cell(0,0,1,0,0,_) ).
cell( 4, cell(0,0,0,1,0,_) ).
cell( 5, cell(0,0,0,0,1,_) ).

block( ?Subject, ?Block )

holds when Block is a cell representation that is incompatible with Subject.

block( 1, cell(0,_,_,_,_,_) ).
block( 2, cell(_,0,_,_,_,_) ).
block( 3, cell(_,_,0,_,_,_) ).
block( 4, cell(_,_,_,0,_,_) ).
block( 5, cell(_,_,_,_,0,_) ).

adjacent_successors( ?Cell, ?AdjacentSuccesors )

holds when AdjacentSuccesors is the set of successors of Cell that are adjacent to it.

adjacent_successors( cell(_,_,_,_,_,AdjacentSuccesors), AdjacentSuccesors ).

blocked( +Blocked, ?Subject )

holds when all the cells in Blocked are incompatible with Subject.

blocked( [], _Subject ).
blocked( [Cell|Blocked], Subject ) :-
    block( Subject, Cell ),
    blocked( Blocked, Subject ).

candidates( ?Subjects, ?Candidates )

holds when there are 4 Candidates for each subject in Subjects.

candidates( [], [] ).
candidates( [Subj|Subjects], [[Subj,Subj,Subj,Subj]|Candidates] ) :-
    candidates( Subjects, Candidates ).

offset( +Element, +List, ?Offset )

When Element has unary Offset from the head of List.

offset( Element, List, Position ) :-
    offset1( List, Element, 0, Position ).

offset1( [Element|_Rest], Element, N, N ).
offset1( [_Head|List], Element, N0, N ):-
    offset1( List, Element, s(N0), N ).

adjacent( +Coordinate0, ?Coordinate1 )

holds when Coordinate0 and Coordinate1 are the same or differ by 1.

adjacent( N, N ).
adjacent( N, s(N) ).
adjacent( s(N), N ).

Load a small library of Puzzle Utilities.

:- ensure_loaded( misc ).

The code is available as plain text here.

Result

This program reports 29870 solutions.