queens.java

JAVA 采用递归的方式实现八皇后问题

import java.util.*;
public class Queens
{
  public static final int BOARD_SIZE = 8; 
  public static final char EMPTY ='*'; 
  public static final char QUEEN ='Q'; 
  private char board[][]; //  棋盘
  public Queens() 
  {
    board = new char[BOARD_SIZE][BOARD_SIZE];
  }          
  public void clearBoard() //  初始化棋盘，全置空
  {
    int i,j;
    for(i=0;i<BOARD_SIZE;i++)
    {
        for(j=0;j<BOARD_SIZE;j++)
               board[i][j] = EMPTY;
    }               
  }
  public void displayBoard() //显示棋盘
  {
    int i,j;
    for(i=0;i<BOARD_SIZE;i++)
    {
        for(j=0;j<BOARD_SIZE;j++)
              System.out.print( "\t"+board[i][j]);
        System.out.println("\n");      
    }   
  }
  public boolean placeQueens(int beginRow,int column)//column列左边的都已经放好了，从beginRow行开始尝试放column列的皇后
  {
    if (column > BOARD_SIZE) 
    {
      return true;
    } 
    else 
    {
      boolean queenPlaced = false;
      int row = beginRow;
      while ( !queenPlaced && (row <= BOARD_SIZE) )  
      {
        if (isUnderAttack(row, column)) 
        {
          ++row;
        }
        else 
        {
          setQueen(row, column);
          queenPlaced = placeQueens(1,column+1);
          if (!queenPlaced)
          {
          	removeQueen(row, column);
            ++row;
          }
        }
      }
      return queenPlaced;
    }
  }
  private void setQueen(int row, int column)
  {
    board[index(row)][index(column)] = QUEEN;
  }
  private void removeQueen(int row, int column) 
  {
    board[index(row)][index(column)] = EMPTY;
  }
  private boolean isUnderAttack(int row, int column) 
  {
  	int r,c;   
    for(c=0;c<index(column);c++)
    {
        for(r=0;r<BOARD_SIZE;r++)
           {
              if(r==index(row)&&board[r][c]==QUEEN)  
              	return true;//同行检测
              if((Math.abs(r-index(row))==Math.abs(c-index(column)))&&(board[r][c]==QUEEN))  
              	return true; //对角线检测                
            }
    }
    return false;
  }
  private int index(int number) 
  {
    if((number >=1) &&( number <= BOARD_SIZE))
       return number-1;
    else
       return 0;
  }
  public static void main(String[] args)
  {
      Queens q = new Queens();
      for(int i=1;i<=Queens.BOARD_SIZE;i++)
      {
        q.clearBoard();  
        if(q.placeQueens(i,1))//
        {
        	System.out.println("Solution NO."+i+":"); 
            q.displayBoard();
        }
        else
           System.out.println("No solution.");
      }
  }
}