artificial intelligence - java:implement 8 queen using depth first search -
i try implement 8 queen using depth search initial state work fine empty board(no queen on board) ,but need work initial state if there solution,if there no solution initial state print there no solution
here code:
public class depth { public static void main(string[] args) { //we create board int[][] board = new int[8][8]; board [0][0]=1; board [1][1]=1; board [2][2]=1; board [3][3]=1; board [4][4]=1; board [5][5]=1; board [6][6]=1; board [7][7]=1; eightqueen(8, board, 0, 0, false); system.out.println("the solution pair"); for(int i=0;i<board.length;i++){ for(int j=0;j<board.length;j++) if(board[i][j]!=0) system.out.println(" ("+i+" ,"+j +")"); } system.out.println("the number of node stored in memory "+count1); } public static int count1=0; public static void eightqueen(int n, int[][] board, int i, int j, boolean found) { long starttime = system.nanotime();//time start if (!found) { if (isvalid(board, i, j)) {//check if position valid board[i][j] = 1; system.out.println("[queen added @ (" + + "," + j + ")"); count1++; printboard(board); if (i == n - 1) {//check if last queen found = true; printboard(board); double endtime = system.nanotime();//end method time double duration = (endtime - starttime)*math.pow(10.0, -9.0); system.out.print("total time"+"= "+duration+"\n"); } //call next step eightqueen(n, board, + 1, 0, found); } else { //if position not valid & if reach last row backtracking while (j >= n - 1) { int[] = backmethod(board, i, j); = a[0]; j = a[1]; system.out.println("back @ (" + + "," + j + ")"); printboard(board); } //we next call eightqueen(n, board, i, j + 1, false); } } } public static int[] backmethod(int[][] board, int i, int j) { int[] = new int[2]; (int x = i; x >= 0; x--) { (int y = j; y >= 0; y--) { //search last queen if (board[x][y] != 0) { //deletes last queen , returns position board[x][y] = 0; a[0] = x; a[1] = y; return a; } } } return a; } public static boolean isvalid(int[][] board, int i, int j) { int x; //check queens in column (x = 0; x < board.length; x++) { if (board[i][x] != 0) { return false; } } //check queens in row (x = 0; x < board.length; x++) { if (board[x][j] != 0) { return false; } } //check queens in diagonals if (!safediag(board, i, j)) { return false; } return true; } public static boolean safediag(int[][] board, int i, int j) { int xx = i; int yy = j; while (yy >= 0 && xx >= 0 && xx < board.length && yy < board.length) { if (board[xx][yy] != 0) { return false; } yy++; xx++; } xx = i; yy = j; while (yy >= 0 && xx >= 0 && xx < board.length && yy < board.length) { if (board[xx][yy] != 0) { return false; } yy--; xx--; } xx = i; yy = j; while (yy >= 0 && xx >= 0 && xx < board.length && yy < board.length) { if (board[xx][yy] != 0) { return false; } yy--; xx++; } xx = i; yy = j; while (yy >= 0 && xx >= 0 && xx < board.length && yy < board.length) { if (board[xx][yy] != 0) { return false; } yy++; xx--; } return true; } public static void printboard(int[][] board) { system.out.print(" "); (int j = 0; j < board.length; j++) { system.out.print(j); } system.out.print("\n"); (int = 0; < board.length; i++) { system.out.print(i); (int j = 0; j < board.length; j++) { if (board[i][j] == 0) { system.out.print(" "); } else { system.out.print("q"); } } system.out.print("\n"); } } } for example initial state give me following error:
exception in thread "main" java.lang.stackoverflowerror i stuck, think error infinite call method how solve problem.
any idea helpful,thanks in advance.
note:the broad 2 dimensional array,when put (1) means there queen @ point.
note2: put initial state following work:
board [0][0]=1; board [1][1]=1; board [2][2]=1; board [3][3]=1; board [4][4]=1; board [5][5]=1; board [6][6]=1; board [7][1]=1;
[edit: added conditional output tip.]
to add @stephenc's answer:
this heck of complicated piece of code, if you're not experienced in programming java.
i executed code, , outputs on , on , on , on (and over)
back @ (0,0) 01234567 0 1 q 2 q 3 q 4 q 5 q 6 q 7 q @ (0,0) and crashes this
exception in thread "main" java.lang.stackoverflowerror @ java.nio.buffer.<init>(unknown source) ... @ java.io.printstream.print(unknown source) @ java.io.printstream.println(unknown source) @ depth.eightqueen(depth.java:56) @ depth.eightqueen(depth.java:60) @ depth.eightqueen(depth.java:60) @ depth.eightqueen(depth.java:60) @ depth.eightqueen(depth.java:60) ... my first instinct add system.out.println(...)s figure out stuff going wrong, won't work here.
the 2 options see to
- get familiar debugger , use step through , analyze why it's never stopping loop
- break down man! how can hope deal massive problem without breaking digestible chunks???
not mention concept of 8-queens complicated begin with.
one further thought:
system.out.println()s not useful implemented, because there's infinite output. debugger better solution here, option somehow limit output. example, create counter @ top
private static final int iiterations = 0; and instead of
system.out.println("[anumberfortracing]: ... useful information ...") use
conditionalsdo((iiterations < 5), "[anumberfortracing]: ... useful information"); here function:
private static final void conditionalsdo(boolean b_condition, string s_message) { if(b_condition) { system.out.println(s_message); } } another alternative not limit output, write file.
i hope information helps you.
(note: edited op's code compilable.)
Comments
Post a Comment