Hi,
First of all I understand that my post has become too long but there was no other way to explain what exactly I am doing and what exactly I am having troubles with. I do value the time that you guys would spent reading my post.
I am working on the knight's tour problem.
I have an empty chessboard (
chessboard[0][0] ) and one knight. The knight has to go through each possible element on the chessboard just once.
Chessboard[8][8]
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
The knight makes only L-shaped moves (two spaces in one direction and one space in a perpendicular direction). Thus from a square near the middle of an empty chessboard, the knight can make eight different moves.
The board is represented by an eight-by-eight two-dimensional array. Each square is initialized to zero.
The first part of the problem is to write an application that moves the knight around the chessboard randomly using the L-shaped moves and going through each position of the chessboard just once. I did this part.
The second part is to do the same but using accessibility heuristic. In this case I have second 8 x 8 array, called
accessibility whose elements are initialized with the following values:
Accessibility[8][8]
2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2
The numbers indicate from how many squares each particular square is accessible. For example, element
accessibility[0][0] is accessible from 2 locations - [2][1] and [1][2].
The most troublesome or inaccessible squares are the four corners.
In this part the knight should always move to the square
with the lowest accessibility number.
In case of a tie, the knight may move to any of the tied squares. Therefore, the tour may begin in any of the four corners. As the knight moves around the chessboard, my application should reduce the accessibility numbers as more squares become occupied.
In this way, at any given time during the tour, each available square’s accessibility number will remain equal to precisely the number of squares from which that square may
be reached.
I did this part as well. I don't think it's good idea to post the whole approx. 300 lines code. Basically what I do:
- Start at any position. For example at [0][0].
-
chessboard[0][0] = 1;
-
accessibility[0][0] = 0; I mark this element as already used, so it's no more usable
- Every possible ( L-shaped moves) accessibility number is decreased by 1. I put all these decreased values in another one-dimensional array positionsArrayPrimary[] and find the minimum
in this array. I get the position of this minimum and based on that value I am changing
row and
column values correspondigly.
So, here I have
Chessboard[][]
*1* 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Accessibility[][]
*0* 3 4 4 4 4 3 2
3 4 *5* 6 6 6 4 3
4 *5* 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2
positionsArrayPrimary[] = {10, 10, 10, 5, 5, 10, 10, 10}; - so, min is at position [3] and position [4]
This method gets the positions of the min and based on that it changes
row and
column accordingly:
private void modifyRowAndColumn(){
switch(minPosition){
case 0:
row -= 2;
column--;
break;
case 1:
row -= 2;
column++;
break;
case 2:
row--;
column += 2;
break;
case 3:
row++;
column += 2;
break;
case 4:
row += 2;
column++;
break;
case 5:
row += 2;
column--;
break;
case 6:
row++;
column -= 2;
break;
case 7:
row--;
column -= 2;
break;
}
}
and goes in the loop again until all the values in the
chessboard[][] == 1;
In the last part of the question I have to write a version of the Knight’s Tour application that, when encountering a tie between two or more squares, decides what square to choose
by looking ahead to those squares reachable from the “tied” squares. My application should move to the tied square for which the next move would arrive at a square with the
lowest accessibility number.
Here I was going to use another array int positionsArraySecondary = new int[8], where to put the values of the "ahead" elements. In other words:
- We are at chessboard[5][4]
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 *1* 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
- We have eight possibilities (I show only the numbers for the example for better readability, '*' denotes the specific element of the array)
Accessibility[][]
********
********
********
***7 *7 **
**7 ***5 *
****0 ***
**5 ***3 *
***3 *3 **
- positionsArrayPrimary[] = {7, 7, 5, 3, 3, 3, 5, 7} - min is at *[3], [4]* and *[5]*
- I am testing Accessibility[6][6] , which is the first min in positionsArrayPrimary[]
First iteration:
********
********
********
********
*****7 *3
****0 *** ----> here it is 0 because I start from there, so I have to keep it zero (inaccessible) while testing the possibilities
******0 *
****3 ***
- positionsArraySecondary[] = {7, 3, 10, 10, 10, 10, 3, 10} ----> min = 3. Since I "came" from position [3] of positionsArrayPrimary[] I need to "keep" this position in order to know how to modify
row and
column later using modifyRowAndColumn() *( troubles with this case since there is duplicate - here I assumed there was no duplicate in order to explain myself better)*
- int positionsMinOfDuplicates[] = new int[8] -----> positionsMinOfDuplicates[3] = 3; (this is the value from the previous step)
- Now I am testing Accessibility[7][5] - the first duplicate
Second iteration:
********
********
********
********
********
****0 *5 * ----> here it is 0 because I start from there, so I have to keep it zero (inaccessible) while testing the possibilities
***5 ***2
*****0 **
- positionsArraySecondary[] = {10, 5, 2, 10, 10, 10, 10, 5} ----> min = 2. I "came" from position [4] of positionsArrayPrimary[] ---> positionsMinOfDuplicates[4] = 2;
- Now I am testing Accessibility[7][3] - the second duplicate
Third iteration:
********
********
********
********
********
**7 *0 *** ----> here it is 0 because I start from there, so I have to keep it zero (inaccessible) while testing the possibilities
*3 ***5 **
***0 ****
- positionsArraySecondary[] = {7, 10, 5, 10, 10, 10, 10, 3} ----> min = 3. I "came" from position [5] of positionsArrayPrimary[] ---> positionsMinOfDuplicates[5] = 3;
- after testing all the possibilities I have positionsMinOfDuplicates[] = {10, 10, 10, 3, 2, 3, 10, 10}; -----> min = 2 at position[4] ----> using modifyRowAndColumn() I go to the
proper element of the chessboard considering the lowest accessibility number.
For the last a couple of days I've been stuck at the last part of the question. I have no idea what to do if I keep having duplicates - this is the case if I start at any of the four corners. Or in the case of the first iteration, where I have positionsArraySecondary[] = {7, 3, 10, 10, 10, 10, 3, 10} - there is duplicate, but I assumed there was no.
I would definitely appreciate any ideas, suggestions or anything that you share with me.
Thanks in advance.