AnonymousVendetta

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;
}