用一个阵列8皇后 [英] 8 Queens using One array

问题描述

  

可能重复：
  <一href="http://stackoverflow.com/questions/3817011/dumb-8-queens-problem-in-c-using-goto-and-backtrack">Dumb使用GOTO和回溯在C ++中8皇后问题

有了解如何使用一维数组实现八皇后问题的问题。也无法弄清楚如何打印阵列打印出所有可能的解决方案。

 的#includestdafx.h中
＃包括＆LT;的iostream＆GT;
使用名字空间std;


诠释的main（）
{
    INT Q [8]。
    Q [0] = 0;
    INT C = 0;
    诠释计数= 0;

NC：C ++;
    如果（C == 8）转到打印;
    Q [C] = -1;

NR：Q [C] =
    如果（Q [C] == 8）转到原路返回;
    的for（int i = 0;我c为C;我++）{
        如果（Q [I] == Q [C] || ABS（Q [C]  -  Q [I]）==（C  -  1））
            GOTO NR;
    }
    转到NC;

回溯：
    C - ;
    如果（C = -1）返回0;
    GOTO NR;

打印：
    ++计数;
    COUT＆LT;＆LT;算上＆LT;＆LT; ENDL;
    的for（int i = 0; I＆LT; = 7;我++）{
            COUT＆LT;＆LT; Q [I];
    }
    COUT＆LT;＆LT; ENDL;
    GOTO原路返回;


    返回0;
}
 

解决方案

首先，使用避免 GOTO ，除非你所面对的问题，其中，goto是唯一正确的方法减少code重复。这不是这些案件之一。 你通常会使用递归来做到这一点。使用一维数组，这个问题意味着递归的最大深度为8（给定的8×8棋盘），所以它不会，除非你的计算机上运行程序要用尽你的筹码这是几十年的历史。

不管怎样，我碰巧使用回溯前，用一维数组已经实施了8皇后问题。 给定一个数组 INT板[8] 和索引我，该指数将是x坐标女王和数组[我] 将存储的y坐标。

例如：

由于

  int数组[8] = {1，3，5，7，2,0，6，4};
 

这是一个有效的解决方案，这将模拟以下主板：

  7 *
6×
5×
4×
3×
2个
1个
0 X
  0 1 2 3 4 5 6 7
 

我不知道该政策是在这里张贴完整的解决问题的方法是什么，但我记得解决这个我自己，我清楚地记得我的造型一般回溯算法差不多的完全的后伪$ C $对回溯维基百科的文章C部分。 考虑使用的一维阵列这里进行了第二的好处。

1. 您不能放置在同一列两个皇后，由于只具有一维数组。这很好，因为它是无效的，反正。
2. 如果您要放置一个皇后在坐标（X，Y）（即阵列[X] = Y ）它是非法的，如果是已经到数组中。
3. 如果您要放置一个皇后在坐标（X，Y）这是非法的，如果存在任何有效的指数 X_1 到阵列和对应的y坐标 Y_1 ，满足条件 ABS（ X_1 - X）== ABS（Y_1 - Y）。

使用这些知识是微不足道的决定皇后有效的展示位置和一切仍然在那之后正在实施的回溯算法。

延伸阅读：

http://www.animatedrecursion.com/advanced/the_eight_queens_problem.html http://en.wikipedia.org/wiki/Backtracking

Possible Duplicate:
Dumb 8 Queens problem in C++ using goto and backtrack

Having problems understanding how to use an one dimensional array to implement the eight queens problem. Also can't figure out how to print the array to print out all possible solutions.

#include "stdafx.h"
#include <iostream>
using namespace std;


int main()
{
    int q[8];
    q[0] = 0;
    int c = 0;
    int count = 0;

NC: c++;
    if (c == 8) goto print;
    q[c] = -1;

NR: q[c] = 
    if (q[c] == 8) goto backtrack; 
    for(int i = 0; i < c; i++){
        if(q[i] == q[c] || abs(q[c] - q[i]) == (c - 1))
            goto NR;
    }
    goto NC;

backtrack:
    c--;
    if(c = -1) return 0;
    goto NR;

Print:
    ++count;
    cout << count << endl;
    for(int i = 0; i <= 7; i++){
            cout << q[i];
    }
    cout << endl;
    goto backtrack;


    return 0;
}

解决方案

First of all, refrain from using goto unless you are facing problems where goto is the only proper way to reduce code duplication. This isn't one of those cases. You would normally use recursion to do this. Using a 1-dimensional array for this problem means that the maximum depth of the recursion will be 8(given a chess board of 8 x 8), so it's not going to be exhausting your stack unless you're running your program on a computer that is several decades old.

Anyway, I happen to have implemented the 8 queens problem using backtracking before, with a 1-dimensional array. Given an array int board[8], and an index i, the index would be the x coordinate for a queen and array[i] would store the y coordinate.

Example:

Given

int array[8] = { 1, 3, 5, 7, 2, 0, 6, 4 };

Which is a valid solution, this would model the following board:

7       x
6             x
5     x  
4               x  
3   x       
2         x 
1 x         
0           x 
  0 1 2 3 4 5 6 7 

I'm not sure what the policy is on posting complete solutions to problems here, but I remember solving this myself and I distinctly remember modeling my general backtracking algorithm almost exactly after the Pseudocode section on the wikipedia article for backtracking. Think about the benefits of using the 1-dimensional array here for a second.

1. You cannot place two queens in the same column due to only having a one dimensional array. That's fine, since it would be invalid, anyway.
2. If you are about to place a queen at coordinate (x, y)(which is array[x] = y) it is illegal if y is already in the array.
3. If you are about to place a queen at coordinate (x, y) it is illegal if there exists any valid index x_1 into array and corresponding y-coordinate y_1 that fulfills the condition abs(x_1 - x) == abs(y_1 - y).

With that knowledge it is trivial to determine valid placements for queens, and all that remains after that is implementing the backtracking algorithm.

Further reading:

http://www.animatedrecursion.com/advanced/the_eight_queens_problem.html http://en.wikipedia.org/wiki/Backtracking

这篇关于用一个阵列8皇后的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！