Thursday, March 10, 2011

Eight Queens - 2

I have tested my code with different board sizes and it is throwing the correct number of solutions :).

When I started thinking of optimization. First thing came in mind was set of strings used for tracking blocked cells. Instead of having different heavy data structure, we can use the same board with different numeric for blocked cell. I have used '-1' for the same.

import java.util.Set;
import java.util.TreeSet;
public class Chess8Queens {
        private static final int BOARD_SIZE = 8;
        private static final int[][] chessBoard = new int[BOARD_SIZE][BOARD_SIZE];
        private static final Set<String> result = new TreeSet<String>();
        static {
               for(int i=0; i < BOARD_SIZE; i++)
                       for(int j=0; j < BOARD_SIZE; j++)
                              chessBoard[i][j] = 0;
        }
        private static void printBoard(boolean isSuccess) {
               StringBuffer sb = new StringBuffer();
               for (int i = 0; i < BOARD_SIZE; i++) {
                       for (int j = 0; j < BOARD_SIZE; j++) {
                               System.out.print(chessBoard[i][j] == -1 

                                                 ? "* " : chessBoard[i][j] + " ");
                               if(chessBoard[i][j] > 0 && isSuccess) 

                                         sb.append(j).append("|");
                       }
                       System.out.println("");
               }
               if(isSuccess) result.add(sb.toString());
               sb = null;
               System.out.println("Done :" + result.size());
        }
        private static void updateBlockedSet(int row, int col, boolean isAdd) {
               int flag1 = 0, flag2 = 0;
               if (col > row) {
                       flag1 = col - row;
                       flag2 = col + row;
                       for (int i = 0; i < BOARD_SIZE; i++) {
                               if (col < BOARD_SIZE)
                                      chessBoard[i][col] = isAdd ? -1 : 0;
                               if (row < BOARD_SIZE && col < BOARD_SIZE)
                                      chessBoard[row][i] = isAdd ? -1 : 0;
                               if ((flag1 + i) < BOARD_SIZE)
                                      chessBoard[i][flag1+i] = isAdd ? -1 : 0;
                               if ((flag2 - i) >= 0 && (flag2 - i) < BOARD_SIZE)
                                      chessBoard[i][flag2-i] = isAdd ? -1 : 0;
                       }
               } else if (col < row) {
                       flag1 = row - col;
                       flag2 = col + row;
                       for (int i = 0; i < BOARD_SIZE; i++) {
                               if (col < BOARD_SIZE)
                                       chessBoard[i][col] = isAdd ? -1 : 0;
                               if (row < BOARD_SIZE)
                                      chessBoard[row][i] = isAdd ? -1 : 0;
                               if ((flag1 + i) < BOARD_SIZE)
                                      chessBoard[flag1+i][i] = isAdd ? -1 : 0;
                               if ((flag2 - i) >= 0 && (flag2 - i) < BOARD_SIZE)
                                      chessBoard[flag2-i][i] = isAdd ? -1 : 0;
                       }
               } else {
                       for (int i = 0; i < BOARD_SIZE; i++) {
                               flag1 = col > (BOARD_SIZE/2) ? (BOARD_SIZE-1)-col : col;
                               flag2 = col + flag1;
                               flag1 = col - flag1;
                               chessBoard[i][col] = isAdd ? -1 : 0;
                               chessBoard[row][i] = isAdd ? -1 : 0;
                               chessBoard[i][i] = isAdd ? -1 : 0;
                               if((flag2-i) >= 0 && (flag2-i) < BOARD_SIZE && 

                                   (flag1 + i) >= 0 && (flag1 + i) < BOARD_SIZE)
                                      chessBoard[flag2-i][flag1+i] = isAdd ? -1 : 0;
                       }
               }
        }
        private static void adjustBadPosition(int row) {
               if(row < 0) return;
               int tempj=0;
               boolean changed = false;
               for(int j= 0; j < BOARD_SIZE; j++ )
                       if(chessBoard[row][j] > 0) {
                               chessBoard[row][j] = 0;
                               tempj = j;
                               changed = true; break;
                       }
               if(changed) {
                       for(int j=tempj+1; j<BOARD_SIZE; j++)
                               chessBoard[row][j] = 0;
                       for(int i=row+1; i<BOARD_SIZE; i++)
                               for(int j= 0; j<BOARD_SIZE; j++ )
                                      chessBoard[i][j] = 0;
                       resetUpdateList();
                       chessBoard[row][tempj] = -1;
               }
        }
        private static void resetUpdateList() {
               for(int i=0; i<BOARD_SIZE; i++)
                       for(int j= 0; j<BOARD_SIZE; j++ )
                               if(chessBoard[i][j] > 0 ) {
                                      int temp = chessBoard[i][j];
                                      updateBlockedSet(i,j,true);
                                      chessBoard[i][j] = temp;
                               }      
        }
        public static Set<String> getPositions() {
               if(result.isEmpty()) {
                       for( int row = 0; row < BOARD_SIZE; row++) {
                               if(row < 0) break;
                               for(int col = 0; col< BOARD_SIZE; col++) {
                                      if(chessBoard[row][col] == 0) {
                                              updateBlockedSet(row,col,true);
                                              chessBoard[row][col] = row+1;
                                              break;
                                      } else if(col == (BOARD_SIZE-1)){
                                              adjustBadPosition(row-1);
                                              row = row - 2; break;
                                      }
                               }
                               if(row == (BOARD_SIZE-1)) {
                                      printBoard(true);
                                      adjustBadPosition(row);
                                      row--;
                               }
                       }
               }
               return result;
        }
        public static void main(String... arg) {
               for(String s: getPositions())
                       System.out.println(s);
               System.out.println(getPositions().size());
        }
}

The output differ slightly from previous as 'B' is getting mixed with 8. I am printing *.

* * * * * * * 1
* * * 2 * * * *
3 * * * * * * *
* * 4 * * * * *
* * * * * 5 * *
* 6 * * * * * *
* * * * * * 7 *
* * * * 8 * * *


Still lot of optimization can be done. Only 12 unique solutions are possible with 8 size board, instead of having many recursive loops, using simple mathematics rest 80 can be generated.

No comments:

Post a Comment