backtracking
This problem gives you a 5x5 chess board with 24 knights ( 12 of them are white and the other 12 are black ) and wants you to turn the board to the initial board that is described in the problem with minimum moves.
I think there are better approaches, because in the rank list the first 20 have solved this problem with time 0.000, but if you implement a careful backtracking you will pass time limit.
Since the depth is just 10, backtracking is sufficient.
I just replaced the empty cell with every possible replacement, except the cell that in previous move was empty.
for(int p = 0; p < 8; p ++) // 8 directions to move from space { // x & y are the previous cell that was empty i = x+dir[p][0]; j = y+dir[p][1]; if( i >= 0 && j >= 0 && i < 5 && j < 5 && ( i != a || j != b ) )
{
swap( input[i][j], input[x][y] );
solve( d+1, x, y );
swap( input[i][j], input[x][y] );
}
}
If the problem is solvable in less than 11 moves, maybe it's possible to solve it in several paths, so each time the puzzle was solved, I saved the length of the shortest path.
No comments:
Post a Comment