8皇后解决方案Java代码的说明. [英] Explanation of 8-Queen solution Java code.
问题描述
我找到了一个8皇后解决方案，可以在Eclipse中进行编译和运行.我相信该解决方案遵循回溯方法，并且工作的实质是在 solution 和 unsafe 函数中完成的，但是我很难理解其中的代码路径.有人可以帮我理解这段代码在做什么.
我的来源- http://rosettacode.org/wiki/N-queens_problem#Java我对照其他来源发布的92个解决方案验证了输出.看起来不错.所以我知道代码有效.
我已尝试对其进行格式化，并添加一些基本注释以清除内容-
private静态int [] b =新的int [8];私有静态整数s = 0;公共静态void main(String [] args){//解决方案来自-http://rosettacode.org/wiki/N-queens_problem#Java新的QueenN();}公开QueenN(){解决方案();}公共无效解决方案(){整数y = 0;b [0] = -1;而(y> = 0){做 {b [y] ++;} while(((b [y]< 8)&& unsafe(y));;如果(b [y]< 8){如果(y< 7){b [++ y] = -1;} 别的 {putboard();}} 别的 {y--;}}}//检查皇后位置是否与其他皇后发生冲突公共静态布尔值unsafe(int y){int x = b [y];对于(int i = 1; i< = y; i ++){int t = b [y-i];如果(t == x || t == x-i || t == x + i){返回true；}}返回false；}//打印解决方案公共静态无效putboard(){System.out.println("\ n \ n解决方案" +(++ s));for(int y = 0; y< 8; y ++){for(int x = 0; x< 8; x ++){如果(b [y] == x)System.out.print("| Q");别的System.out.print("| _");}System.out.println("|");}} 结束.
让我们尝试逐步理解代码.首先，我们调用函数solution()，这导致执行谜题答案.
溶液功能:
public void solution(){整数y = 0;b [0] = -1;而(y> = 0){做 {b [y] ++;//如果最后一个单元格不安全，或者我们到达了棋盘的末端，则进入下一行.} while(((b [y]< 8)&& unsafe(y));;//检查是否是最后一个单元格，以及它是否是不安全的单元格(发生冲突)if(b [y]< 8){//我们找到了一个安全的单元格.万岁！if(y< 7){//我们放置了最后一个女王吗?b [++ y] = -1;//不，让我们分配下一个.} 别的 {putboard();//是的，让我们打印结果！}} else {//如果未找到单个安全单元，我们将重新分配最后一个女王.y--;}}} 第一次，您将遍历行(或列，但是您更喜欢它.这只是轮换问题)中的每个单元格.在每个单元格上进行不安全(y)检查，以防万一您放置女王的单元格与其他被女王占据的单元格发生冲突(如您已经在注释中找到的那样).
下一步，一旦我们找到了放置实际皇后(y)的安全单元格，我们就会进行安全检查:如果我们没有找到该皇后区的单个安全单元格，则必须重新分配最后一个皇后区
如果找到该单元格并且该单元格正确，我们将检查它是否为最后一个女王(y <7).如果是这样，我们将继续打印结果.否则，我们只需将b [++ y] = -1重新启动while循环.
不安全功能:
公共静态布尔不安全(int y){int x = b [y];//让我们将实际单元格称为"x"for(int i = 1; i< = y; i ++){//对于放置在实际皇后之前的每个皇后，我们必须检查它是否在同一行，列或对角线中.int t = b [y-i];如果(t == x || t == x-i || t == x + i){返回true；//哦，哦，冲突！}}返回false；//是的，没有冲突！} 此函数检查我们使用的皇后是否与该皇后之前分配的任何皇后发生冲突.冲突可能会在对角线，垂直或水平方向发生:这就是为什么在返回真"语句之前进行三次或"检查的原因.
面板功能:
public static void putboard(){System.out.println("\ n \ n解决方案" +(++ s));for(int y = 0; y< 8; y ++){for(int x = 0; x< 8; x ++){如果(b [y] == x)System.out.print("| Q");别的System.out.print("| _");}System.out.println("|");}} 我将不深入解释这一功能，因为它只是一个相当简单的行打印功能，您可以在执行解决方案时自行了解它的工作原理！
希望这会有所帮助.
干杯！
I found a 8-Queen solution that I was able to compile and run in Eclipse. I believe this solution follows the backtracking approach and meat of the work is done in the solution and unsafe functions, but I am having a hard time understanding the code paths in there. Can someone please help me understand what this code is doing.
My Source - http://rosettacode.org/wiki/N-queens_problem#Java I verified the output against the 92 solutions published on other sources. Looks good. So I know the code works.
I have tried to format it and add some basic notes to clear things up -
private static int[] b = new int[8];
private static int s = 0;
public static void main(String[] args) {
// solution from - http://rosettacode.org/wiki/N-queens_problem#Java
new QueenN();
}
public QueenN() {
solution();
}
public void solution() {
int y = 0;
b[0] = -1;
while (y >= 0) {
do {
b[y]++;
} while ((b[y] < 8) && unsafe(y));
if (b[y] < 8) {
if (y < 7) {
b[++y] = -1;
} else {
putboard();
}
} else {
y--;
}
}
}
// check if queen placement clashes with other queens
public static boolean unsafe(int y) {
int x = b[y];
for (int i = 1; i <= y; i++) {
int t = b[y - i];
if (t == x || t == x - i || t == x + i) {
return true;
}
}
return false;
}
// printing solution
public static void putboard() {
System.out.println("\n\nSolution " + (++s));
for (int y = 0; y < 8; y++) {
for (int x = 0; x < 8; x++) {
if (b[y] == x)
System.out.print("|Q");
else
System.out.print("|_");
}
System.out.println("|");
}
}
End.
Let's try to understand the code step by step. First of all, we call the function solution(), which is what leads to the execution of the puzzle answer.
Solution funcion:
public void solution() {
int y = 0;
b[0] = -1;
while (y >= 0) {
do {
b[y]++; //if last cell was unsafe or we reached the end of the board, we go for the next row.
} while ((b[y] < 8) && unsafe(y)); //Checks whether it's the last cell and if it's an unsafe cell (clashing)
if (b[y] < 8) { //We found a safe cell. Hooray!
if (y < 7) { //Did we place the last queen?
b[++y] = -1; //Nope, let's allocate the next one.
} else {
putboard(); //Yup, let's print the result!
}
} else { //If not a single safe cell was found, we reallocate the last queen.
y--;
}
}
}
On the first while, you're going to iterate through each cell in a row (or column, however you prefer it. It's just a rotation matter). On each cell you make the unsafe(y) check, which will return true in case the cell you're placing the queen in is clashing with other queen-occupied cells (as you've already found out in the comment).
Next step, once we've found a safe cell in which to place the actual queen (y), we make a security check: if we have not found a single safe cell for that queen, we have to reallocate last queen.
In case the cell was found and was correct, we check whether it was the last queen (y < 7). If it is so, we proceed to print the result. Otherwise, we just re-start the while loop by placing b[++y] = -1.
Unsafe function:
public static boolean unsafe(int y) {
int x = b[y]; //Let's call the actual cell "x"
for (int i = 1; i <= y; i++) { //For each queen before placed BEFORE the actual one, we gotta check if it's in the same row, column or diagonal.
int t = b[y - i];
if (t == x || t == x - i || t == x + i) {
return true; //Uh oh, clash!
}
}
return false; //Yay, no clashes!
}
This function checks whether the queen we're using clashes with any of the allocated queens before this one. The clashes might happen diagonally, vertically or horizontally: That is why there is a triple OR check before the "return true" statement.
Putboard function:
public static void putboard() {
System.out.println("\n\nSolution " + (++s));
for (int y = 0; y < 8; y++) {
for (int x = 0; x < 8; x++) {
if (b[y] == x)
System.out.print("|Q");
else
System.out.print("|_");
}
System.out.println("|");
}
}
I'm not gonna explain this one that deep, because it is simply a fairly simply line printing function which you can find out how it works by yourself when executing the solution!
Hope this helps.
Cheers!
这篇关于8皇后解决方案Java代码的说明.的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
