8 Queens using One array

Question

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;
}

Answer 1

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