hello guys please can you help me
i represent the problem as a graph and then i used the A* algorithm whit heuristic equals to the out of place knights it converges rapidly to the answer but i don't know where exatly the problem
here is my code
Code: Select all
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Vector;
class State implements Comparable<State>{
String value;
int hn;
int gn=1;
int fn;
@Override
public String toString() {
return value+" "+hn+"\n";
}
public int compareTo(State s) {
if(this.fn==s.fn) return 0;
else if(this.fn>s.fn) return 1;
else return -1;
}
}
public class Knights_in_FEN {
static char[][] initCong = {{'w','b','w','b','b'}, // sample
{'b','b','w','e','b'},
{'w','b','b','b','w'},
{'w','b','w','b','w'},
{'w','w','b','w','w'}};
static char[][] goal = {{'b','b','b','b','b'},
{'w','b','b','b','b'},
{'w','w','e','b','b'},
{'w','w','w','w','b'},
{'w','w','w','w','w'}};
static Vector<String> visited = new Vector<String>();
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
StringBuffer reslut = new StringBuffer("");
int n = Integer.valueOf(in.nextLine());
for (int i = 0; i <n; i++) {
visited.clear();
for (int j = 0; j < 5; j++) {
String t = in.nextLine();
for (int k = 0; k < 5; k++) {
if(t.charAt(k)==' ') initCong[j][k]='e';
if(t.charAt(k)=='1') initCong[j][k]='b';
if(t.charAt(k)=='0') initCong[j][k]='w';
}
}
State first = new State();
first.value=boardToString(initCong);
int nbr_steps = A_start(first);
if(nbr_steps!=-1) {
if(i!=n-1) reslut.append("Solvable in "+nbr_steps+" move(s).\n");
else reslut.append("Solvable in "+nbr_steps+" move(s).");
}
else{
if(i!=n-1) reslut.append("Unsolvable in less than 11 move(s).\n");
else reslut.append("Unsolvable in less than 11 move(s).");
}
}
System.out.print(reslut);
}
static String boardToString(char[][] board){
String sboard="";
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
sboard+=board[i][j];
}
}
return sboard;
}
static char[][] StringToBoard(String sboard){
char[][] board = new char[5][5];
int i=0,j=0;
for (int k = 0; k < sboard.length(); k++) {
board[i][j]=sboard.charAt(k);
j++;
if(j==5){
j=0;
i++;
}
}
return board;
}
static void printState(char[][] board){
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
System.out.print(board[i][j]+" ");
}
System.out.println();
}
}
static boolean canImoveTo(char[][] board,int i,int j){
if(i>=5 || j>=5 || i<0 || j<0 || board[i][j]!='e') return false;
return true;
}
static int heuristic(char[][] board){
int h=0;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if(board[i][j]!=goal[i][j]) h++;
}
}
return h;
}
static Vector<State> getNextStates(State state){
Vector<State> nextstates = new Vector<State>();
char[][] board;
State s;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
board=StringToBoard(state.value);
if(board[i][j]!='e'){
if(canImoveTo(board, i+1,j+2)){
board[i+1][j+2]=board[i][j];
board[i][j]='e';
s = new State();
s.value=boardToString(board);
s.hn=heuristic(board);
nextstates.add(s);
board=StringToBoard(state.value);
}
if(canImoveTo(board, i+1,j-2)){
board[i+1][j-2]=board[i][j];
board[i][j]='e';
s = new State();
s.value=boardToString(board);
s.hn=heuristic(board);
nextstates.add(s);
board=StringToBoard(state.value);
}
if(canImoveTo(board, i+2,j+1)){
board[i+2][j+1]=board[i][j];
board[i][j]='e';
s = new State();
s.value=boardToString(board);
s.hn=heuristic(board);
nextstates.add(s);
board=StringToBoard(state.value);
}
if(canImoveTo(board, i+2,j-1)){
board[i+2][j-1]=board[i][j];
board[i][j]='e';
s = new State();
s.value=boardToString(board);
s.hn=heuristic(board);
nextstates.add(s);
board=StringToBoard(state.value);
}
if(canImoveTo(board, i-1,j+2)){
board[i-1][j+2]=board[i][j];
board[i][j]='e';
s = new State();
s.value=boardToString(board);
s.hn=heuristic(board);
nextstates.add(s);
board=StringToBoard(state.value);
}
if(canImoveTo(board, i-1,j-2)){
board[i-1][j-2]=board[i][j];
board[i][j]='e';
s = new State();
s.value=boardToString(board);
s.hn=heuristic(board);
nextstates.add(s);
board=StringToBoard(state.value);
}
if(canImoveTo(board, i-2,j+1)){
board[i-2][j+1]=board[i][j];
board[i][j]='e';
s = new State();
s.value=boardToString(board);
s.hn=heuristic(board);
nextstates.add(s);
board=StringToBoard(state.value);
}
if(canImoveTo(board, i-2,j-1)){
board[i-2][j-1]=board[i][j];
board[i][j]='e';
s = new State();
s.value=boardToString(board);
s.hn=heuristic(board);
nextstates.add(s);
board=StringToBoard(state.value);
}
}
}
}
return nextstates;
}
static int A_start(State s0){
PriorityQueue<State> queue = new PriorityQueue<State>();
queue.add(s0);
String sgoal = boardToString(goal);
while(!queue.isEmpty()){
State s = queue.poll();
if(s.gn>10) return -1;
if(s.value.compareTo(sgoal)==0) return s.gn-1;
visited.add(s.value);
Vector<State> nextstates = getNextStates(s);
for (int i = 0; i < nextstates.size(); i++) {
if(!visited.contains(nextstates.elementAt(i))){
nextstates.elementAt(i).gn+=s.gn;
nextstates.elementAt(i).fn=nextstates.elementAt(i).gn+nextstates.elementAt(i).hn;
queue.add(nextstates.elementAt(i));
}
}
}
return -1;
}
}
or if someone of you does have some samples of inputs and correct outputs for this problem.
my solution gives as a result for some samples :
Code: Select all
9
01011
110 1
01110
01010
00100
10110
01 11
10111
01001
00000
11111
01111
00 11
00001
00000
11111
01111
00110
00001
000 0
11111
0111
00111
00001
00000
11111
00111
00111
0 001
00000
11011
110 1
00110
01010
00100
11111
01111
0011
00001
00000
11111
01111
0001
10001
00000
Unsolvable in less than 11 move(s).
Solvable in 7 move(s).
Solvable in 0 move(s).
Solvable in 3 move(s).
Solvable in 1 move(s).
Solvable in 8 move(s).
Unsolvable in less than 11 move(s).
Solvable in 2 move(s).
Solvable in 4 move(s).
