Головоломка "12 доминирующих рыцарей"
Я искал несколько часов и пока не нашел полностью работающего решения для такого рода головоломки. Таким образом, я следовал за подобной проблемой с епископами.
Что мне нужно сделать, так это разместить 12 коней на шахматной доске таким образом, чтобы все свободные квадраты доски были атакованы хотя бы одной фигурой.
Конечный результат должен выглядеть так:
Проблема в что моя программа пробует разные комбинации только с двумя последними частями, а затем как-то вылетает. РЕДАКТИРОВАНИЕ
Что я сделал до сих пор:
#include <iostream>
using namespace std;
#define N 8
void fillChessBoard(int (&chessBoard)[N][N], int num);
void printChessBoard(int (&chessBoard)[N][N]);
void removeKnight(int (&chessBoard)[N][N], int i, int j);
void placeKnight(int (&chessBoard)[N][N], int i, int j);
bool allSpaceDominated(int (&chessBoard)[N][N]);
bool backtracking(int (&chessBoard)[N][N], int pos);
int main()
{
int chessBoard[N][N];
fillChessBoard(chessBoard, 0);
backtracking(chessBoard, 0);
return 0;
}
bool backtracking(int (&chessBoard)[N][N], int knightNum)
{
if(knightNum==12)
{
if(allSpaceDominated(chessBoard))
{
printChessBoard(chessBoard);
return true;
}
else return false;
}
else
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
if(chessBoard[i][j]!=2)
{
placeKnight(chessBoard, i, j);
printChessBoard(chessBoard); //step by step
if(backtracking(chessBoard, knightNum+1)) return true;
removeKnight(chessBoard, i, j);
}
}
}
}
}
void fillChessBoard(int (&chessBoard)[N][N], int num)
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
chessBoard[i][j]=num;
}
}
}
void printChessBoard(int (&chessBoard)[N][N])
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
cout<<chessBoard[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
cout<<endl;
cin.get();
}
void removeKnight(int (&chessBoard)[N][N], int i, int j)
{
int num=0;
chessBoard[i][j]=num;
if(i+2 <= N && j+1 <= N && chessBoard[i+2][j+1]!=2) chessBoard[i+2][j+1]=num;
if(i+2 <= N && j-1 >= 0 && chessBoard[i+2][j-1]!=2) chessBoard[i+2][j-1]=num;
if(i-2 >= 0 && j+1 <= N && chessBoard[i-2][j+1]!=2) chessBoard[i-2][j+1]=num;
if(i-2 >= 0 && j-1 >= 0 && chessBoard[i-2][j-1]!=2) chessBoard[i-2][j-1]=num;
if(i+1 <= N && j+2 <= N && chessBoard[i+1][j+2]!=2) chessBoard[i+1][j+2]=num;
if(i+1 <= N && j-2 >= 0 && chessBoard[i+1][j-2]!=2) chessBoard[i+1][j-2]=num;
if(i-1 >= 0 && j+2 <= N && chessBoard[i-1][j+2]!=2) chessBoard[i-1][j+2]=num;
if(i-1 >= 0 && j-2 >= 0 && chessBoard[i-1][j-2]!=2) chessBoard[i-1][j-2]=num;
for(int k=0; k<N; k++) //correct overlapping dominations
{
for(int x=0; x<N; x++)
{
if(chessBoard[k][x]==2)
{
placeKnight(chessBoard, k, x);
}
}
}
}
void placeKnight(int (&chessBoard)[N][N], int i, int j)
{
int num=1;
chessBoard[i][j]=2;
if(i+2 <= N && j+1 <= N && chessBoard[i+2][j+1]!=2) chessBoard[i+2][j+1]=num;
if(i+2 <= N && j-1 >= 0 && chessBoard[i+2][j-1]!=2) chessBoard[i+2][j-1]=num;
if(i-2 >= 0 && j+1 <= N && chessBoard[i-2][j+1]!=2) chessBoard[i-2][j+1]=num;
if(i-2 >= 0 && j-1 >= 0 && chessBoard[i-2][j-1]!=2) chessBoard[i-2][j-1]=num;
if(i+1 <= N && j+2 <= N && chessBoard[i+1][j+2]!=2) chessBoard[i+1][j+2]=num;
if(i+1 <= N && j-2 >= 0 && chessBoard[i+1][j-2]!=2) chessBoard[i+1][j-2]=num;
if(i-1 >= 0 && j+2 <= N && chessBoard[i-1][j+2]!=2) chessBoard[i-1][j+2]=num;
if(i-1 >= 0 && j-2 >= 0 && chessBoard[i-1][j-2]!=2) chessBoard[i-1][j-2]=num;
}
bool allSpaceDominated(int (&chessBoard)[N][N])
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
if(chessBoard[i][j]==0) return false;
}
}
return true;
}
Редактировать:
Исправлены границы массива вplaceKnight
а такжеremoveKnight
(например, j + 2 <N вместо j + 2 <= N)добавленнойreturn false;
вbacktracking
Проблема: Теперь это зацикливается навсегда. Пробует множество комбинаций, но никогда не находит ту, которая мне нужна (перебор?)
#include <iostream>
using namespace std;
#define N 8
void fillChessBoard(int (&chessBoard)[N][N], int num);
void printChessBoard(int (&chessBoard)[N][N]);
void removeKnight(int (&chessBoard)[N][N], int i, int j);
void placeKnight(int (&chessBoard)[N][N], int i, int j);
bool allSpaceDominated(int (&chessBoard)[N][N]);
bool backtracking(int (&chessBoard)[N][N], int pos);
int main()
{
int chessBoard[N][N];
fillChessBoard(chessBoard, 0);
backtracking(chessBoard, 0);
printChessBoard(chessBoard);
return 0;
}
bool backtracking(int (&chessBoard)[N][N], int knightNum)
{
if(knightNum==12)
{
if(allSpaceDominated(chessBoard))
{
printChessBoard(chessBoard);
return true;
}
else return false;
}
else
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
if(chessBoard[i][j]!=2)
{
placeKnight(chessBoard, i, j);
printChessBoard(chessBoard);// step by step
if(backtracking(chessBoard, knightNum+1)) return true;
removeKnight(chessBoard, i, j);
}
}
}
return false; //ADDED LINE
}
}
void fillChessBoard(int (&chessBoard)[N][N], int num)
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
chessBoard[i][j]=num;
}
}
}
void printChessBoard(int (&chessBoard)[N][N])
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
cout<<chessBoard[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
cout<<endl;
//cin.get();
}
void removeKnight(int (&chessBoard)[N][N], int i, int j)
{
int num=0;
chessBoard[i][j]=num;
if(i+2 < N && j+1 < N && chessBoard[i+2][j+1]!=2) chessBoard[i+2][j+1]=num;
if(i+2 < N && j-1 >= 0 && chessBoard[i+2][j-1]!=2) chessBoard[i+2][j-1]=num;
if(i-2 >= 0 && j+1 < N && chessBoard[i-2][j+1]!=2) chessBoard[i-2][j+1]=num;
if(i-2 >= 0 && j-1 >= 0 && chessBoard[i-2][j-1]!=2) chessBoard[i-2][j-1]=num;
if(i+1 < N && j+2 < N && chessBoard[i+1][j+2]!=2) chessBoard[i+1][j+2]=num;
if(i+1 < N && j-2 >= 0 && chessBoard[i+1][j-2]!=2) chessBoard[i+1][j-2]=num;
if(i-1 >= 0 && j+2 < N && chessBoard[i-1][j+2]!=2) chessBoard[i-1][j+2]=num;
if(i-1 >= 0 && j-2 >= 0 && chessBoard[i-1][j-2]!=2) chessBoard[i-1][j-2]=num;
for(int k=0; k<N; k++)
{
for(int x=0; x<N; x++)
{
if(chessBoard[k][x]==2)
{
placeKnight(chessBoard, k, x);
}
}
}
}
void placeKnight(int (&chessBoard)[N][N], int i, int j)
{
int num=1;
chessBoard[i][j]=2;
if(i+2 < N && j+1 < N && chessBoard[i+2][j+1]!=2) chessBoard[i+2][j+1]=num;
if(i+2 < N && j-1 >= 0 && chessBoard[i+2][j-1]!=2) chessBoard[i+2][j-1]=num;
if(i-2 >= 0 && j+1 < N && chessBoard[i-2][j+1]!=2) chessBoard[i-2][j+1]=num;
if(i-2 >= 0 && j-1 >= 0 && chessBoard[i-2][j-1]!=2) chessBoard[i-2][j-1]=num;
if(i+1 < N && j+2 < N && chessBoard[i+1][j+2]!=2) chessBoard[i+1][j+2]=num;
if(i+1 < N && j-2 >= 0 && chessBoard[i+1][j-2]!=2) chessBoard[i+1][j-2]=num;
if(i-1 >= 0 && j+2 < N && chessBoard[i-1][j+2]!=2) chessBoard[i-1][j+2]=num;
if(i-1 >= 0 && j-2 >= 0 && chessBoard[i-1][j-2]!=2) chessBoard[i-1][j-2]=num;
}
bool allSpaceDominated(int (&chessBoard)[N][N])
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
if(chessBoard[i][j]==0) return false;
}
}
return true;
}