关于java 八皇后的问题
之前的帖子也有发过。这一次让重新写这个作业，要求是一样的。还是没太搞明白，求大神支援。要求在下面，要读要求，必须是二位char array并且method必须按照他的要求写十分感谢！
• Name the class EightQueens
• Make all the required methods public
• Represent the chessboard as an instance variable, a two-dimensional char array. Use the char Q for a queen and o (lower case letter O) for an empty space
• The class must support a deep copy through a method called clone()
• When an object is created, it should return an empty chessboard (that is, one filled with o)
• getBoard() returns the current state of the chessboard
• setQueen(int row, int column) marks the square as Q
• emptySquare(int row, int column) marks the square as o
• setQueens(int queensRemaining) returns boolean (success or failure of placement). It sets the specified number of queens in allowed positions on the board. Note that the board may already have queens placed on it
• The solution should employ recursion
• Placement of the queens must be calculated by your program, rather than hardcoded
/**
@author Rui Guan <a href="mailto:rui.guan@ucalgary.ca">
rui.guan@ucalgary.ca</a>
@version 1.9
@since 1.0
*/
/*
This is a program which can place any number of queens, up to a maximum of 8, on a
an 8x8 grid chessboard such that no queen can attack any other queens.
*/
public class EightQueens implements Cloneable{
@Override
public EightQueens clone() throws CloneNotSupportedException {
// TODO Auto-generated method stub
return (EightQueens) super.clone();
}
public static void main(String[] args) {
EightQueens a=new EightQueens();
System.out.println(a.setQueens(6));
a.print();
System.out.println(a.setQueens(1));
a.print();
}
private char chessboard[][];
private boolean queens[];
private int queenNum;
//constructor
public EightQueens() {
//the new object is empty
chessboard=new char[8][8];
queens = new boolean[8];
queenNum = 0;
for(int i=0;i<8;i++) {
queens[i] = false;
for(int j=0;j<8;j++) {
emptySquare(i,j);
}
}
}
//method getBoard
public char[][] getBoard() {
return chessboard;
}
//method setQueen: put Q into the square
public void setQueen (int row, int column) {
chessboard[row][column]='Q';
}
//method emptySquare: put o into empty square
public void emptySquare(int row, int column){
chessboard[row][column]='o';
}
//method setQueens: put the specific amount of chess into it
public boolean setQueens(int queensRemaining){
// 少于0了，不行
if(queensRemaining < 0) {
return false;
}
// 已有的皇后数目和需要摆放的皇后数目，加起来超过8了，不行
if(queenNum + queensRemaining > 8){
return false;
}
// 只需要放0个皇后，可以的
if(queensRemaining == 0){
return true;
}
// 看看哪儿有空地方
for(int i = 0; i < 8; i ++){
if(queens[i])continue;
for(int j = 0; j < 8; j++){
boolean flag = rule(i, j);
if(flag){
// 能放就放
setQueen(i, j);
queenNum++;
queens[i] = true;
// 看看其他位置还能不能放
boolean flag2 = setQueens(queensRemaining-1);
if(flag2){
// 能放，得嘞
return true;
}
else{
// 不能放，拉倒
queenNum--;
queens[i] = false;
emptySquare(i, j);
}
}
}
}
return false;
}
// check if the space is available for queens
public boolean rule(int u,int v){
for(int i = 0; i < 8; i++) {
// 同行是冤家
if (chessboard[i][v] == 'Q') {
return false;
}
// 同列也打架
if (chessboard[u][i] == 'Q') {
return false;
}
}
int i = u, j = v;
while(i >= 0 && i < 8 && j >= 0 && j < 8){
// 主对角线往上找
if(chessboard[i][j]=='Q')return false;
i--;
j--;
}
i = u;
j = v;
while(i >= 0 && i < 8 && j >= 0 && j < 8){
// 主对角线往下找
if(chessboard[i][j]=='Q')return false;
i++;
j++;
}
i = u;
j = v;
while(i >= 0 && i < 8 && j >= 0 && j < 8){
// 副对角线往上找
if(chessboard[i][j]=='Q')return false;
i++;
j--;
}
i = u;
j = v;
while(i >= 0 && i < 8 && j >= 0 && j < 8){
// 副对角线往下找
if(chessboard[i][j]=='Q')return false;
i--;
j++;
}
return true;
}
//This is just for test
public void print(){
for(int i=0;i<8;i++){
for(int m=0;m<8;m++){
System.out.print(chessboard[i][m]+" ");
}
System.out.print("\n");
}
System.out.print("\n");
}
}
package test.recursion;
/**
* @author shkstart
* @create 2021-01-08 11:41
*/
//用一维数组代替二维数组 arr[8]={0 4 7 5 2 6 1 3] 0代表第一个皇后放在第一行第一列 4代表第二个皇后放在第二行第5列
//7代表第三个放在第三行第8列 .....省去判断不同皇后同行的可能
public class EightQueens {
int max = 8; //皇后个数
static int count = 0; //判断有几种解法
static int num = 0; //判断检测冲突次数
int[] arr = new int[max];
public static void main(String[] args) {
queue8 queue8 = new queue8();
queue8.check(0);
System.out.println(count);
System.out.println(num);
}
//递归
private void check(int n) {//n 为0-7，代表第n+1个皇后
if (n == max) {
print(); //n=8 退出
return;
}
//依次放，并判断OK?
for (int i = 0; i < max; i++) {
arr[n] = i;
if (adjust(n)) {
check(n + 1); //如果不冲突，接着放n+1
} else {//关键
//adjust(4)在i=0时不冲突，进入adjust（5），如果冲突了，即adjust（5）=i(i=0)冲突了，将不执行adjust（6），而是进行for循环，adjust（5）=i（i=1），继续判断冲突...
//如果adjust（5）=i遍历全部仍然冲突，将回溯到adjust(4)，进行遍历，即adjust(4)在i=1时
//包含了多层嵌套
}
}
}
//检测是否冲突
private boolean adjust(int n) {
num++;
for (int i = 0; i < n; i++) {
if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[n] - arr[i])) //同一列或者||斜线 类似斜率 arr[i]代表的是第i+1个的所在列数+1
return false;
}
return true;
}
//打印输出 ，每输出一次，即为一种解法，参考check（）的该方法的使用
private void print() {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
count++;
System.out.println();
}
}