Sunday, March 6, 2011

Eight Queens

Eight Queens problem :
The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that none of them can capture any other using the standard chess queen's moves.



I really enjoyed solving Eight queens problem manually as well as programatically. 

Initially my code was returning 98. I literally diged a mountain to find the small rat (A small condition issue was throwing extra 6 wrong combination). Now I am getting unique 92 combination :). 

Thank you very much 'Ranga Vure' for pointing out the issue.


import java.util.Set;
import java.util.TreeSet;


public class Chess8Queens {


   private static final int chessBoard[][] = {{0, 0, 0, 0, 0, 0, 0, 0},
                                              {0, 0, 0, 0, 0, 0, 0, 0},
                                              {0, 0, 0, 0, 0, 0, 0, 0},
                                              {0, 0, 0, 0, 0, 0, 0, 0},
                                              {0, 0, 0, 0, 0, 0, 0, 0},
                                              {0, 0, 0, 0, 0, 0, 0, 0},
                                              {0, 0, 0, 0, 0, 0, 0, 0},
                                              {0, 0, 0, 0, 0, 0, 0, 0}};
   private static final Set<String> blockedList = new TreeSet<String>();
   private static final Set<String> result = new TreeSet<String>();
   private static void printBoard(boolean isSuccess) {
      StringBuffer sb = new StringBuffer();
      for (int i = 0; i < 8; i++) {
         for (int j = 0; j < 8; j++) {
            System.out.print(chessBoard[i][j] == 0 ?
                                 blockedList.contains(i + "" + j) ? "B " : "O "
                                 : 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;
      boolean temp;
      if (col > row) {
         flag1 = col - row;
         flag2 = col + row;
         for (int i = 0; i < 8; i++) {
            if (col < 8) {
               temp = isAdd ? blockedList.add(i + "" + col + "")
                            : blockedList.remove(i + "" + col + "");
            }
            if (row < 8 && col < 8) {
                temp = isAdd ? blockedList.add(row + "" + i + "")
                             : blockedList.remove(row + "" + i + "");
            }
            if ((flag1 + i) < 8) {
                temp = isAdd ? blockedList.add(i + "" + (flag1 + i) + "")
                             : blockedList.remove(i + "" + (flag1 + i) + "");
            }
            if ((flag2 - i) < 8) {
                temp = isAdd ? blockedList.add(i + "" + (flag2 - i) + "")
                             : blockedList.remove(i + "" + (flag2 - i) + "");
             }
        }
     } else if (col < row) {
        flag1 = row - col;
        flag2 = col + row;
        for (int i = 0; i < 8; i++) {
           if (col < 8) {
              temp = isAdd ? blockedList.add(i + "" + col + "")
                           : blockedList.remove(i + "" + col + "");
           }
           if (row < 8) {
              temp = isAdd ? blockedList.add(row + "" + i + "")
                           : blockedList.remove(row + "" + i + "");
           }
           if ((flag1 + i) < 8) {
              temp = isAdd ? blockedList.add((flag1 + i) + "" + (i) + "")
                           : blockedList.remove((flag1 + i) + "" + (i) + "");
           }
           if ((flag2 - i) < 8) {
              temp = isAdd ? blockedList.add((flag2 - i) + "" + (i) + "")
                           : blockedList.remove((flag2 - i) + "" + (i) + "");
           }
        }
    } else {
       for (int i = 0; i < 8; i++) {
          flag1 = col > 4 ? 7-col : col;
          flag2 = col + flag1;
          flag1 = col - flag1;
          temp = isAdd ? blockedList.add(i + "" + col + "")
                       : blockedList.remove(i + "" + col + "");
          temp = isAdd ? blockedList.add(row + "" + i + "")
                       : blockedList.remove(row + "" + i + "");
          temp = isAdd ? blockedList.add(i + "" + i + "")
                       : blockedList.remove(i + "" + i + "");
          if((flag2-i) >= 0 && (flag2-i) < 8 && (flag1 + i) >= 0 && (flag1 + i) < 8)
              temp = isAdd ? blockedList.add((flag2-i) + "" + (flag1 + i))
                           : blockedList.remove((flag2-i) + "" + (flag1 + i));
       }
    }
  }
  private static boolean adjustBadPosition(int row) {
     int tempj=0;
     boolean changed = false;
     for(int j= 0; j<8; j++ ) {
        if(chessBoard[row][j] != 0) {
           chessBoard[row][j] = 0;
           tempj = j;
           changed = true;
        }
     }
     if(changed) {
        for(int j=tempj+1; j<8; j++)
            blockedList.remove(row+""+j);
        for(int i=row+1; i<8; i++) {
           for(int j= 0; j<8; j++ ) {
              chessBoard[i][j] = 0;
              blockedList.remove(i+""+j);
           }
        }
        resetUpdateList();
        blockedList.add(row+""+tempj);
        return true;
     }
     return false;
  }
  private static void resetUpdateList() {
     for(int i=0; i<8; i++) {
        for(int j= 0; j<8; j++ ) {
           if(chessBoard[i][j] != 0 ) {
               updateBlockedSet(i,j,true);
           }
        }
     }
   }
   public static Set<String> getPositions() {
      if(result.isEmpty()) {
         for( int row = 0; row < 8; row++) {
            if(row < 0) break;
            for(int col = 0; col< 8; col++) {
               if(!blockedList.contains(row+""+col)) {
                  chessBoard[row][col] = row+1;
                  updateBlockedSet(row,col,true);
                  break;
               } else if(col == 7){
                  adjustBadPosition(row-1);
                  row = row -2;
                  break;
               }

            }
            if(row == 7) {
               printBoard(true);
               adjustBadPosition(row);
               row--;
            }

         }
     }
     return result;
   }


   public static void main(String... arg) {
      //System.out.println(result);
      System.out.println(getPositions().size());
   }
}


Sample output :

1 B B B B B B B

B B B B 2 B B B
B B B B B B B 3
B B B B B 4 B B
B B 5 B B B B B
B B B B B B 6 B
B 7 B B B B B B
B B B 8 B B B B
Done1

92 positions :  I have listed only columns.
0|4|7|5|2|6|1|3| = 0,0 | 1,4| 2,7 | 3,5| 4,2| 5,6 | 6,1| 7,3 = Top Listed board
0|5|7|2|6|3|1|4|
0|6|3|5|7|1|4|2|
0|6|4|7|1|3|5|2|
1|3|5|7|2|0|6|4|
1|4|6|0|2|7|5|3|
1|4|6|3|0|7|5|2|
1|5|0|6|3|7|2|4|
1|5|7|2|0|3|6|4|
1|6|2|5|7|4|0|3|
1|6|4|7|0|3|5|2|
1|7|5|0|2|4|6|3|
2|0|6|4|7|1|3|5|
2|4|1|7|0|6|3|5|
2|4|1|7|5|3|6|0|
2|4|6|0|3|1|7|5|
2|4|7|3|0|6|1|5|
2|5|1|4|7|0|6|3|
2|5|1|6|0|3|7|4|
2|5|1|6|4|0|7|3|
2|5|3|0|7|4|6|1|
2|5|3|1|7|4|6|0|
2|5|7|0|3|6|4|1|
2|5|7|0|4|6|1|3|
2|5|7|1|3|0|6|4|
2|6|1|7|4|0|3|5|
2|6|1|7|5|3|0|4|
2|7|3|6|0|5|1|4|
3|0|4|7|1|6|2|5|
3|0|4|7|5|2|6|1|
3|1|4|7|5|0|2|6|
3|1|6|2|5|7|0|4|
3|1|6|2|5|7|4|0|
3|1|6|4|0|7|5|2|
3|1|7|4|6|0|2|5|
3|1|7|5|0|2|4|6|
3|5|0|4|1|7|2|6|
3|5|7|1|6|0|2|4|
3|5|7|2|0|6|4|1|
3|6|0|7|4|1|5|2|
3|6|2|7|1|4|0|5|
3|6|4|1|5|0|2|7|
3|6|4|2|0|5|7|1|
3|7|0|2|5|1|6|4|
3|7|0|4|6|1|5|2|
3|7|4|2|0|6|1|5|
4|0|3|5|7|1|6|2|
4|0|7|3|1|6|2|5|
4|0|7|5|2|6|1|3|
4|1|3|5|7|2|0|6|
4|1|3|6|2|7|5|0|
4|1|5|0|6|3|7|2|
4|1|7|0|3|6|2|5|
4|2|0|5|7|1|3|6|
4|2|0|6|1|7|5|3|
4|2|7|3|6|0|5|1|
4|6|0|2|7|5|3|1|
4|6|0|3|1|7|5|2|
4|6|1|3|7|0|2|5|
4|6|1|5|2|0|3|7|
4|6|1|5|2|0|7|3|
4|6|3|0|2|7|5|1|
4|7|3|0|2|5|1|6|
4|7|3|0|6|1|5|2|
5|0|4|1|7|2|6|3|
5|1|6|0|2|4|7|3|
5|1|6|0|3|7|4|2|
5|2|0|6|4|7|1|3|
5|2|0|7|3|1|6|4|
5|2|0|7|4|1|3|6|
5|2|4|6|0|3|1|7|
5|2|4|7|0|3|1|6|
5|2|6|1|3|7|0|4|
5|2|6|1|7|4|0|3|
5|2|6|3|0|7|1|4|
5|3|0|4|7|1|6|2|
5|3|1|7|4|6|0|2|
5|3|6|0|2|4|1|7|
5|3|6|0|7|1|4|2|
5|7|1|3|0|6|4|2|
6|0|2|7|5|3|1|4|
6|1|3|0|7|4|2|5|
6|1|5|2|0|3|7|4|
6|2|0|5|7|4|1|3|
6|2|7|1|4|0|5|3|
6|3|1|4|7|0|2|5|
6|3|1|7|5|0|2|4|
6|4|2|0|5|7|1|3|
7|1|3|0|6|4|2|5|
7|1|4|2|0|6|3|5|
7|2|0|5|1|4|6|3|
7|3|0|2|5|1|6|4|

No comments:

Post a Comment