CrowdedChess Class Reference
[Scripts for problems]
Inherits Example.
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 
, where the number of pieces to place are:
queens- rooks
bishops
knights where k is a number to maximize.
The maximum k for some different values of 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:
| Q | B | K | . | K | B | K | R |
| . | K | . | K | Q | K | R | B |
| B | . | K | R | K | . | K | Q |
| B | K | R | K | . | Q | . | B |
| B | R | Q | . | K | . | K | B |
| R | K | . | K | . | K | Q | B |
| B | Q | K | . | K | R | K | . |
| B | K | B | Q | R | K | B | B |
Definition at line 183 of file crowded-chess.cc.
Public Types | |
| enum | { PROP_TUPLE_SET, PROP_DECOMPOSE } |
Public Member Functions | |
| CrowdedChess (const SizeOptions &opt) | |
| 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 (std::ostream &os) |
| Print solution. | |
Protected Types | |
| enum | { Q, R, B, K, E, PMAX } |
Protected Member Functions | |
| bool | valid_pos (int i, int j) |
| void | knight_constraints (void) |
| 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 |
Related Functions | |
| (Note that these are not member functions.) | |
| TupleSet | bishops |
| Set of valid positions for the bishops. | |
| void | init_bishops (int size) |
| Initialize bishops. | |
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 194 of file crowded-chess.cc.
| anonymous enum |
- Enumerator:
-
PROP_TUPLE_SET Propagate bishops placement extensionally. PROP_DECOMPOSE Propagate bishops placement with decomposition.
Definition at line 228 of file crowded-chess.cc.
Constructor & Destructor Documentation
| CrowdedChess::CrowdedChess | ( | const SizeOptions & | opt | ) | [inline] |
| CrowdedChess::CrowdedChess | ( | bool | share, | |
| CrowdedChess & | e | |||
| ) | [inline] |
Member Function Documentation
| bool CrowdedChess::valid_pos | ( | int | i, | |
| int | j | |||
| ) | [inline, protected] |
Definition at line 204 of file crowded-chess.cc.
| void CrowdedChess::knight_constraints | ( | void | ) | [inline, protected] |
| virtual Space* CrowdedChess::copy | ( | bool | share | ) | [inline, virtual] |
| virtual void CrowdedChess::print | ( | std::ostream & | os | ) | [inline, virtual] |
Friends And Related Function Documentation
| void init_bishops | ( | int | size | ) | [related] |
Member Data Documentation
const int CrowdedChess::n [protected] |
IntVarArray CrowdedChess::s [protected] |
IntVarArray CrowdedChess::queens [protected] |
IntVarArray CrowdedChess::rooks [protected] |
BoolVarArray CrowdedChess::knights [protected] |
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:
- examples/crowded-chess.cc (Revision: 6033)