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();

}

}``````
3
Contributors
3
Replies
4
Views
7 Years
Discussion Span
Last Post by 0x69

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.

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

Edited by nunos: n/a

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;
}
}``````
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.