27. Knight Tour

Warnsdorff's algorithm

//---------------------------------------------------------------------------

# define DIR 8

struct Cood

{   int dx, dy;

};

struct Step

{   int x, y;

};

struct Move

{   struct Step pos;

    int moves;

};

struct Cood offset[DIR];

//------------------ Set up the offset table for the knight moves

{   offset[0].dx = -2; offset[0].dy = 1;   offset[1].dx = -1; offset[1].dy = 2;

    offset[2].dx =  1; offset[2].dy = 2;   offset[3].dx =  2; offset[3].dy = 1;

    offset[4].dx =  2; offset[4].dy = -1;  offset[5].dx =  1; offset[5].dy = -2;

    offset[6].dx = -1; offset[6].dy = -2;  offset[7].dx = -2; offset[7].dy = -1;

}

struct Move next[DIR];     // next is an array of 8 element with type struct Move

struct Step step;

int K[50][50];

int n;

struct Step nextMove(struct Step step, int k) 

{   struct Step test;

    test.x = step.x+offset[k].dx;  test.y = step.y+offset[k].dy;

    return test;    // return the next step of the current step

}

bool InBoard(struct Step test)  // check  whether test is within the board

{   return (test.x >= 0 && test.x < n) && (test.y >= 0 && test.y < n);

}

bool Empty(struct Step test)    // Check  whether test is an empty cell

{   return (K[test.x][test.y]==0);

}

bool KnightTour(struct Step step)

{   int data, k, nSquare = n*n, cnt, p, min, i, j;

    struct Step test;

    K[step.x][step.y] = 1;    // set the starting step

    for (data=2; data <= nSquare; data++)

    {   for (cnt=0, k=0; k<DIR; k++)   // collect all legal next steps in next[]

        {   test = nextMove(step, k);

            if (InBoard(test) && Empty(test))

            {   next[cnt].pos  = test; // record test as a legal next move

        next[cnt++].moves= 0;   // init/reset the #moves 

            }

        }    // cnt counts the total number of legal moves of the current step

       if (cnt == 0) break;  // No solution!

       for (p=0; p<cnt; p++)  // compute each legal move's next moves

       {   step = next[p].pos;  // step.x = next[p].x;  step.y = next[p].y;

           for (k=0; k<DIR; k++)

           {     test = nextMove(step, k);

                 if (InBoard(test) && Empty(test))

                      next[p].moves++; 

                      // test is a legal move for step (one of the next moves)

           }

        }    // all legal moves' next moves are computed

        for (min=0, i=1; i<cnt; i++)   

            if (next[i].moves < next[min].moves) min = i;

             // find the next move which has the minimum next moves

        step = next[min].pos;

        K[step.x][step.y] = data;  // step is the next move

    }

    return (data > nSquare);

}

//------------------------------

n = Edit1->Text.ToInt();

for (i=0; i<n; i++)

   for (j=0; j<n; j++)

       K[i][j] = 0;

TabSheet3->Show();

start.x = (CheckBox2->Checked) ? rand()%n : Edit2->Text.ToInt();

start.y = (CheckBox2->Checked) ? rand()%n : Edit3->Text.ToInt();

bool tour = KnightTour(start);

printKnight(n);

if (tour)

   Memo1->Lines->Add("(x, y) = ("+IntToStr(start.x)+", "+IntToStr(start.y)+") O");

else Memo1->Lines->Add("(x, y) = ("+IntToStr(start.x)+", "+IntToStr(start.y)+") X");