# It's the same?, problem with the king of chess

Posted 10 years ago
15394 Views
|
7 Replies
|
9 Total Likes
|
 Given an nxn chessboard size, a king is placed in a boxarbitrary coordinate ( x , y) . The problem is to determine the n ^ 2-1Figure 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 solutionk contain a natural number indicating the order number that has beenaccessed box coordinates ( x , y) .The algorithm works in stages at each stage k deciding where tomoves . As there are eight possible moves in each step , this will be themaximum number of children that will be generated by each node .As for explicit restrictions , the way in which we definedstructure representing the solution ( in this case a two dimensional array ofnatural) numbers , we know that its components can be numbersbetween 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 whogenerated 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 restrictionsI 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]
7 Replies
Sort By:
Posted 10 years ago
 It is amazing!, Ilian Gachevski, I worked very hard in the solution, but cannot find,thanks for your help, is invaluable, greetings everybody
Posted 10 years ago
 To translate the Modula-2 code faithfully, a local variable should be global and a weak inequality should be strict.
Posted 10 years ago
 Thanks Todd for you help, but when performed the change, my program fall in a loop, you believe the conversion of the loop UNTIL is bad?, or the parameters are out of domain, because me not finding the solution, I will work in that, I hope someone can help me. Greetings
Posted 10 years ago
 Sorry I missed this the first time.  It should be While[orden<8 && !exito, which is the translation of do{} while (odern>=8 || exito)Try using ArrayPlot to visualize the answer.  You can also make a more sophisticated graphic with Arrow.
Posted 10 years ago
 Hello, I've made ??the changes in the cycle WHILE, but when running the program with the following entry rey[1,1,1], mathematica is very busy and can only be stopped by using the command to abort , it is the combination ctrl +,.I show you in the picture belowI hope your instructios for this case, greetings and thanks in advance
Posted 10 years ago
 here is the solution according to the code that I showed at the beginning,that our approach would be to{{12,1,2,3},{13,11,4,5},{14,10,6,7},{15,16,9,8}} placed in the variable tablero. my problem is that mathematica, repeat some numbers in the solution, as seen in the example of rey[1,1,1], any idea is welcome, greetings guys
Posted 10 years ago
 Try replacingIf[! exito, tablero[[u, v]] == 0]withIf[! exito, tablero[[u, v]] = 0]It would be interesting to see a Mathematica solution in a more native style.