C++ Backtracking puzzle

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

Aš turiu N rikių lentoje problemą padaręs.

Pora minčių apie kodą:

• 
   
  
• Kiekvieną kartą tikrindamas ar uždavinys jau išspręstas tu pereini visą šachmatų lentą. Daug greičiau būtų tikrinti vieną skaičių, kuris parodo kiek dabar okupuotų langelių yra ir jį vis atnaujinti, kai yra padedamos ar nuimamos figūros. Dabar kiekvienam tikrinimui reikia 64 palyginimo operacijų, o darydamas kaip sakiau operacijų skaičių turbūt sumažintum iki ~20 (neskaičiavau tiksliai).
  
• Lentos spausdinimas į ekraną turėtų užimti labai daug laiko. Nedaryk to, spausdink tik atsakymą.
  
• Kai tikrini ar galima dėti naują žirgą, tai tu tik patikrini ar tame langelyje nėra žirgo. Žirgo reikėtų nedėti ir tada, kai tas langelis okupuotas.
  
• Išmesk for ciklą iš removeKnight funkcijos. Kaip supratu jis reikalingas tam, kad nuėmus žirgą vėl teisingai būtų sužymėti okupuoti langeliai, bet manau, kad žirgų ant okupuotų langelių iš vis nereikėtų dėti.
  
• Esu parašęs šią programą ant prolog, bet tau kodas turbūt nepadėtų, nes tikėtina, kad jo nesuprastum :D
  

Edit:

Pasirodo aš apie kiek kitokį uždavinį galvojau, kuriame turi būti uždengta visa lenta, bet negali būti žirgų, kurie kerta kitus žirgus. Oh well.

Tas lengvas kur negali kirst vienas kito, nes šitame variante žymiai daugiau galimybių yra.

Netinkamai dėliojami žirgai. Dabar bandoma sudėti 12 žirgų, o dedant kiekvieną žirgą peržiūrima visi 64 langeliai. Taigi iš viso išeina 12⁶⁴ ≈ 10⁶⁹ iteracijų. O ką iš tikro reikia padaryti tai pasirūpinti, kad visi langeliai būtų kertami. Iš viso tokių langelių yra 64, o kiekvienam langeliui yra viso labo iki 8 pozicijų, kuriose pastatytas žirgas galėtų kirsti tą langelį. Išeina viso labo 64⁸ ≈ 3×10¹³ (čia grubiais skaičiavimais, realiai kažkiek mažiau, nes pėdejus vieną žirgą liko neokupuoti ne 63, o nuo 56 iki 62 langelių) variantų, ir tai yra kur kas mažiau.

Kita svarbi priemonė yra stengtis kuo anksčiau numatyti, kad nebepavyks užpildyti visos lentos. Turint omeny kad vienas žirgas gali okupuoti iki 8 langelių, jei žirgų liko 5, bet neokupuotų langelių daugiau nei 40, tai toliau gilinti paieškos neapsimoka – reikia grįžti atgal ir bandyti kitaip dėlioti žirgus.

Ir be abejo, reikėtų išnaudoti simetriją – jeigu radai vieną žirgų išdėstymą, tai iš tikro radai keturis – plius veidronis atspindys vertikaliai, horizontaliai ir per lentos centrą (nebent pradinis išdėstymas ir taip jau simetriškas).