Восемь Queens C ++ с использованием стека Backtracking

Так что я делаю это для домашней работы, и я не могу понять, где моя ошибка. Любая помощь очень ценится.

Мое понимание таково.

  1. Инициализировать стек для отслеживания какой строки & В колонке есть королева.
  2. Поместите ферзя в первый квадрат и поместите его в стек. Толчок (0,0); Затем установите переменную, чтобы строка была заполнена. заполненный +;

3. Затем цикл

проверьте, есть ли у текущей строки или столбца конфликт с другой матрицей.

а. нет конфликта толкать в стек. увеличить переменную заполненной строки. заполнены ++; двигаться вверх на ряд.

б. есть конфликт. Двигаться вправо. цв ++;

с. больше не могу двигаться вправо. вытолкните стек и установите в строку и столбец. вычесть заполненный. затем подвинься. цв ++; и попробуй еще раз.


int main(){bool board[8][8];

for(int i = 0; i < 8; i++){
for(int j = 0; j < 8; j++){
board[i][j] = false;}}

int row = 0, col = 0, filled = 0;

StackLi<int> rowStack;
StackLi<int> colStack;

rowStack.push(row);
colStack.push(col);

board[row][col] = true;
//cout << "push: " << "(" << row << "," << col << ")" << endl;
row++;while(filled < 7)
{
if(!isSafe(board,row,col) )
{
filled++;
rowStack.push(row);
colStack.push(col);
board[row][col] = true;
//cout << "push: " << "(" << row << "," << col << ")" << endl;
if(filled > 8)
{
print(board);
return 0;
}
row++;
}
else{
col++;
//cout << "move: " << "(" << row << "," << col << ")" << endl;
}

if(col > 7)
{
row = rowStack.topAndPop();
col = colStack.topAndPop();
board[row][col] = false;
cout << "pop: " << "(" << row << "," << col << ")" << endl;
filled--;
}

}

return 0;

}

bool isSafe(bool board[8][8], int row, int col)
{for(int i = 0; i < 8; i++)
{
if(board[row][i] || board[i][col]) return true;
}

for(int i = 0; (row - i)>=0 && (col-i) >= 0; i++)
{
if(board[row-i][col-i]) return true;
}

for(int i = 0; (row - i)<=8 && (col-i) >= 0; i++)
{
if(board[row+i][col+i]) return true;
}

return false;

}

1

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]