Sveiki, reikia parasyti programa - isdelioti 12 zirgu, kad visi laukai butu okupuoti. Apacioj Brute-force kodas, su pilnu perrinkimu, kuris uzsiloopina amzinybei. Kaip butu imanoma apriboti perrinkimu skaiciu?
1 - okupuota vieta
2 - knightas
0 - tuscia
Rezultatas turetu buti:
http://i.stack.imgur.com/ZNPL2.png
#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;
}
C++ Backtracking puzzle
Programuotojų kampas
Sukurta
Sveiki, reikia parasyti programa - isdelioti 12 zirgu, kad visi laukai butu okupuoti. Apacioj Brute-force kodas, su pilnu perrinkimu, kuris uzsiloopina amzinybei. Kaip butu imanoma apriboti perrinkimu skaiciu?
1 - okupuota vieta
2 - knightas
0 - tuscia
Rezultatas turetu buti:
http://i.stack.imgur.com/ZNPL2.png