## 10422 - Knights in FEN

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10422 - Knights in FEN

Yes I know it's WA code, it's exactly the same code you posted as being WA code. Run your code on this input (copied from Sedefcho's post above):

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``````
If the output you get doesn't match:

Code: Select all

``````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).``````
(and it doesn't). Then that might help explain why that code is getting WA.
Check input and AC output for thousands of problems on uDebug!

afruizc
New poster
Posts: 15
Joined: Sat Oct 13, 2012 2:04 am

### Re: 10422 - Knights in FEN

Im getting WA and I don't know why. My code passes all I/O posted int this thread. The idea is to run BFS for the first 10 layers, then stop. After that, I get the input and see if there is a solutions so far. If there is, I output it, if not, I output the "Unsolvable in less than 11 move(s).".

Here is my code:

Code: Select all

``````Cut after AC
``````
Last edited by afruizc on Wed Dec 12, 2012 10:00 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10422 - Knights in FEN

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

New poster
Posts: 6
Joined: Thu Dec 20, 2012 9:25 pm

### 10422 - Knights in FEN : WA !!!

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);
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);
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);
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);
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);
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);
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);
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);
board=StringToBoard(state.value);
}

}
}
}

return nextstates;
}

static int A_start(State s0){

PriorityQueue<State> queue = new PriorityQueue<State>();
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;

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;
}
}
}

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).``````