Example: Crowded chessboard More...
Public Types | |
enum | { PROP_TUPLE_SET, PROP_DECOMPOSE } |
Public Member Functions | |
CrowdedChess (const SizeOptions &opt) | |
The model of the problem. More... | |
CrowdedChess (bool share, CrowdedChess &e) | |
Constructor for cloning e. More... | |
virtual Space * | copy (bool share) |
Copy during cloning. More... | |
virtual void | print (std::ostream &os) const |
Print solution. More... | |
![]() | |
ScriptBase (void) | |
Default constructor. More... | |
ScriptBase (bool share, ScriptBase &e) | |
Constructor used for cloning. More... | |
virtual void | compare (const Space &, std::ostream &os) const |
Compare with s. More... | |
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. More... | |
Protected Attributes | |
const int | n |
Board-size. More... | |
IntVarArray | s |
The board. More... | |
IntVarArray | queens |
Row of queen in column x. More... | |
IntVarArray | rooks |
Row of rook in column x. More... | |
BoolVarArray | knights |
True iff the corresponding place has a knight. More... | |
enum CrowdedChess:: { ... } | piece |
Related Functions | |
(Note that these are not member functions.) | |
TupleSet | bishops |
Set of valid positions for the bishops. More... | |
void | init_bishops (int size) |
Initialize bishops. More... | |
int | main (int argc, char *argv[]) |
Main function. More... | |
Additional Inherited Members | |
![]() | |
static std::ostream & | select_ostream (const char *name, std::ofstream &ofs) |
Choose output stream according to name. More... | |
template<class Script , template< class > class Engine, class Options > | |
static void | run (const Options &opt, Script *s=NULL) |
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:
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 187 of file crowded-chess.cpp.
|
inline |
The model of the problem.
Definition at line 238 of file crowded-chess.cpp.
|
inline |
Constructor for cloning e.
Definition at line 344 of file crowded-chess.cpp.
|
inlineprotected |
Definition at line 208 of file crowded-chess.cpp.
|
inlineprotected |
Post knight-constraints.
Definition at line 214 of file crowded-chess.cpp.
|
inlinevirtual |
Copy during cloning.
Definition at line 354 of file crowded-chess.cpp.
|
inlinevirtual |
Print solution.
Reimplemented from Gecode::Driver::ScriptBase< BaseSpace >.
Definition at line 360 of file crowded-chess.cpp.
|
related |
Set of valid positions for the bishops.
Definition at line 61 of file crowded-chess.cpp.
|
related |
Initialize bishops.
Definition at line 108 of file crowded-chess.cpp.
|
related |
Main function.
Definition at line 402 of file crowded-chess.cpp.
|
protected |
Board-size.
Definition at line 189 of file crowded-chess.cpp.
|
protected |
The board.
Definition at line 190 of file crowded-chess.cpp.
|
protected |
Row of queen in column x.
Definition at line 191 of file crowded-chess.cpp.
|
protected |
Row of rook in column x.
Definition at line 191 of file crowded-chess.cpp.
|
protected |
True iff the corresponding place has a knight.
Definition at line 193 of file crowded-chess.cpp.
enum { ... } CrowdedChess::piece |
Symbolic names of pieces. The order determines which piece will be placed first.