Message Boards Message Boards

1
|
15933 Views
|
7 Replies
|
9 Total Likes
View groups...
Share
Share this post:

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

Posted 11 years ago
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]
POSTED BY: Luis Ledesma
7 Replies
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 BY: Todd Rowland
To translate the Modula-2 code faithfully, a local variable should be global and a weak inequality should be strict.
POSTED BY: Ilian Gachevski
Posted 11 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 BY: Luis Ledesma
Try replacing

If[! exito, tablero[[u, v]] == 0]

with

If[! exito, tablero[[u, v]] = 0]

It would be interesting to see a Mathematica solution in a more native style.
POSTED BY: Todd Rowland
Posted 11 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 BY: Luis Ledesma
Posted 11 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 BY: Luis Ledesma
Posted 11 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 below


I hope your instructios for this case, greetings and thanks in advance
POSTED BY: Luis Ledesma
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract