8 Queens Problem

[nunos]

I started learning about backtracking in college and was asked to solve the famous 8 queens problem. I know there are many solutions out there for this, but I would like to get there by myself. However, I am kind of stuck and in need for some guidance here.

The problem is that I don't have quite understood how to backtrack properly.

When it comes to the point that there are no more legal positions at the board, I remove the last queen placed, but the algo will place the queen again at the same place that originated no valid positions. I thought about storing the sequences that are invalid so that they are not repeated but I am sure that's not the way to go about it.

Any opinion or pointer in the right direction is greatly appreciated.

Thanks.

package queens;

public class Queens
{
    private int[][] board = new int[9][9];
    private int numQueens = 0;

    public void printBoard()
    {
        for (int i = 1; i <= 8; i++)
        {
            for (int j = 1; j <= 8; j++)
                System.out.printf("%2d", board[i][j]);

            System.out.print("\n");
        }

        System.out.print("\n");
    }

    public void place(int i, int j)
    {
        board[i][j] = 1;
        numQueens++;
    }

    public boolean accepts(int i, int j)
    {
        int row, col;
        row = 1; while (row <= 8) if (board[row++][j] == 1) return false;
        col = 1; while (col <= 8) if (board[i][col++] == 1) return false;
        row = i; col = j; while (row <= 8 && col <= 8) if (board[row++][col++] == 1) return false;
        row = i; col = j; while (row <= 8 && col >= 1) if (board[row++][col--] == 1) return false;
        row = i; col = j; while (row >= 1 && col <= 8) if (board[row--][col++] == 1) return false;
        row = i; col = j; while (row >= 1 && col >= 1) if (board[row--][col--] == 1) return false;
        return true;
    }

    public void remove(int i, int j)
    {
        board[i][j] = 0;
        numQueens--;
    }

    public boolean isComplete()
    {
        return numQueens == 8;
    }

    public boolean calc()
    {
        if (isComplete())
            return true;

        int last_i = 0, last_j = 0;
        
        for (int i = 1; i <= 8; i++)
        {
            for (int j = 1; j <= 8; j++)
            {
                if (accepts(i, j))
                {
                    place(i, j);
                    printBoard();
                    last_i = i;
                    last_j = j;
                   
                }
            }
        }

        remove(last_i, last_j);

       calc();

    }

}

[BestJewSinceJC]

I don't know what the 8 queens problem is. You'd be better off posting this in the Computer Science forum and giving a description of the problem if it is an algorithm question and not strictly a java programming question.

[nunos]

Any moderator can plz move this to computer science section? Or should I double post?

[0x69]

No need to store "bad" sequences at all. Backtracking algorithm skeleton is simple. Pseudocode:

int queen_positions[8]
queen_index = -1
goback = false
While(NOT_SOLVED) {
  if not goback {
    queen_index++
  }
  queen_positions[queen_index] = next legal position from [1..64]
  if no_legal_position_for(queen_index) {
     queen_index--
     goback = true
  }
  else {
     goback = false;
  }
}