Generated on Wed Nov 1 15:04:51 2006 for Gecode by doxygen 1.4.5

CrowdedChess Class Reference
[Example scripts (models)]

Inherits Example.

List of all members.

Detailed Description

Example: Crowded Chessboard

"You are given a chessboard together with 8 queens, 8 rooks, 14 bishops, and 21 knights. The puzzle is to arrange the 51 pieces on the chessboard so that no queen shall attack another queen, no rook attack another rook, no bishop attack another bishop, and no knight attack another knight. No notice is to be taken of the intervention of pieces of another type from that under consideration - that is, two queens will be considered to attack one another although there may be, say, a rook, a bishop, and a knight between them. It is not difficult to dispose of each type of piece separately; the difficulty comes in when you have to find room for all the arrangements on the board simultaneously." Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

This puzzle can be generalized to chess-boards of size $n$ , where the number of pieces to place are:

The maximum k for some different values of $ n $ are presented below (from Jesper Hansen and Joachim Schimpf, ECLiPSe solution
n k
8 21
9 29
10 37
11 47
12 57
13 69
14 81
15 94
16 109

A solution for n = 8 is:
QBK. KBKR
.K.K QKRB
B.KR K.KQ
BKRK .Q.B
BRQ. K.KB
RK.K .KQB
BQK. KRK.
BKBQ RKBB

Todo:
Currently this script finds a solution. Instead, it should find the maximum number of knights for a given size.

Definition at line 103 of file crowded-chess.cc.

Public Member Functions

 CrowdedChess (const Options &o)
 The model of the problem.
 CrowdedChess (bool share, CrowdedChess &e)
 Constructor for cloning e.
virtual Space * copy (bool share)
 Copy during cloning.
virtual void print (void)
 Print solution.

Protected Types

enum  {
  Q, R, B, K,
  E, PMAX
}

Protected Member Functions

bool valid_pos (int i, int j)
void knight_constraints ()
 Post knight-constraints.

Protected Attributes

const int n
 Board-size.
IntVarArray s
 The board.
IntVarArray queens
 Row of queen in column x.
IntVarArray rooks
 Row of rook in column x.
BoolVarArray knights
 True iff the corresponding place has a knight.
enum CrowdedChess:: { ... }  piece

Member Enumeration Documentation

anonymous enum [protected]
 

Symbolic names of pieces. The order determines which piece will be placed first.

Enumerator:
Q  Queen.
R  Rook.
B  Bishop.
K  Knight.
E  Empty square.
PMAX  Number of pieces (including empty squares).

Definition at line 114 of file crowded-chess.cc.

Constructor & Destructor Documentation

CrowdedChess::CrowdedChess (  const Options &  o  )  [inline]
 

The model of the problem.

Definition at line 149 of file crowded-chess.cc.

CrowdedChess::CrowdedChess (  bool  share,
CrowdedChess &  e
)  [inline]
 

Constructor for cloning e.

Definition at line 250 of file crowded-chess.cc.

Member Function Documentation

bool CrowdedChess::valid_pos (  int  i,
int  j
)  [inline, protected]
 

Definition at line 124 of file crowded-chess.cc.

void CrowdedChess::knight_constraints (   )  [inline, protected]
 

Post knight-constraints.

Definition at line 130 of file crowded-chess.cc.

virtual Space* CrowdedChess::copy (  bool  share  )  [inline, virtual]
 

Copy during cloning.

Implements Gecode::Space.

Definition at line 260 of file crowded-chess.cc.

virtual void CrowdedChess::print (  void   )  [inline, virtual]
 

Print solution.

Reimplemented from Example.

Definition at line 266 of file crowded-chess.cc.

Member Data Documentation

const int CrowdedChess::n [protected]
 

Board-size.

Definition at line 105 of file crowded-chess.cc.

IntVarArray CrowdedChess::s [protected]
 

The board.

Definition at line 106 of file crowded-chess.cc.

IntVarArray CrowdedChess::queens [protected]
 

Row of queen in column x.

Definition at line 107 of file crowded-chess.cc.

IntVarArray CrowdedChess::rooks [protected]
 

Row of rook in column x.

Definition at line 107 of file crowded-chess.cc.

BoolVarArray CrowdedChess::knights [protected]
 

True iff the corresponding place has a knight.

Definition at line 109 of file crowded-chess.cc.

enum { ... } CrowdedChess::piece [protected]
 

Symbolic names of pieces. The order determines which piece will be placed first.

The documentation for this class was generated from the following file: