Given an nxn chessboard size, a king is placed in a box
arbitrary coordinate ( x , y) . The problem is to determine the n ^ 2-1
Figure movements so that all board squares are visited once, if there is such a sequence of movements .
The solution to the problem can be expressed as a matrix of dimension nxn representing the chessboard. Each element ( x , y) of this matrix solution
k contain a natural number indicating the order number that has been
accessed box coordinates ( x , y) .
The algorithm works in stages at each stage k deciding where to
moves .
As there are eight possible moves in each step , this will be the
maximum number of children that will be generated by each node .
As for explicit restrictions , the way in which we defined
structure representing the solution ( in this case a two dimensional array of
natural) numbers , we know that its components can be numbers
between zero (indicating that a cell has not been visited yet) n ^ 2 , which is the order of the last possible move . Initially the board is filled with zeros and there is a 1 only in the original box ( x0 , y0 ) .
Implied restrictions in this case will limit the number of children who
generated from a square by checking the movement does not take the king off the board or on a box previously visited .
Having defined the structure that represents the solution and the restrictions
I will use to implement the algorithm that solves the problem just use the general scheme , obtaining :
The mov_x and mov_y variables contain the legal moves of a King
(according to the rules of chess), and are initialized at the beginning of the main program by MovimientosPosibles case:
I have implemented well in Mathematica
movx[1] = 0; movx[2] = -1; movx[3] = -1; movx[4] = -1; movx[5] = 0;
movx[6] = 1; movx[7] = 1; movx[8] = 1;
movy[1] = 1; movy[2] = 1; movy[3] = 0; movy[4] = -1; movy[5] = -1;
movy[6] = -1; movy[7] = 0; movy[8] = 1;
rey[k_, x_, y_] := Module[{orden, exito, u, v},
orden = 0;
exito = False;
While[orden < 8 \[Or] exito,
orden++;
u = x + movx[orden];
v = y + movy[orden];
If[(1 <= u) && (u <= n) && (1 <= v) && (v <=
n) && (tablero[[u, v]] == 0),
tablero[[u, v]] = k;
If[k <= n^2,
rey[k + 1, u, v];
If[! exito, tablero[[u, v]] == 0]
,
exito = True;
]
]
];
MatrixForm[tablero]
]
n = 4;
tablero = Array[0 &, {n, n}];
rey[1,1,1]