ปัญหาราชินี

ปัญหานี้คือการหาการจัดเรียงของราชินี N บนกระดานหมากรุก เพื่อไม่ให้ราชินีตัวใดสามารถโจมตีราชินีตัวอื่นๆ บนกระดานได้

ราชินีหมากรุกสามารถโจมตีได้ทุกทิศทาง ทั้งแนวนอน แนวตั้ง แนวนอน และแนวทแยง

เมทริกซ์ไบนารีใช้เพื่อแสดงตำแหน่งของ N Queens ซึ่งไม่มีราชินีใดสามารถโจมตีควีนตัวอื่นได้

อินพุตและเอาต์พุต

Input:
The size of a chess board. Generally, it is 8. as (8 x 8 is the size of a normal chess board.)
Output:
The matrix that represents in which row and column the N Queens can be placed.
If the solution does not exist, it will return false.

1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0

In this output, the value 1 indicates the correct place for the queens.
The 0 denotes the blank spaces on the chess board.

อัลกอริทึม

isValid(บอร์ด แถว col)

อินพุต: กระดานหมากรุก แถว และคอลัมน์ของกระดาน

ผลลัพธ์ − จริงเมื่อวางราชินีในแถวและวางตำแหน่งที่ถูกต้องหรือไม่

Begin
   if there is a queen at the left of current col, then
      return false
   if there is a queen at the left upper diagonal, then
      return false
   if there is a queen at the left lower diagonal, then
      return false;
   return true //otherwise it is valid place
End

solveNQueen(บอร์ด, คอลัมน์)

อินพุต - กระดานหมากรุก ที่ซึ่งราชินีกำลังพยายามจะวาง

ผลลัพธ์ − เมทริกซ์ตำแหน่งที่วางราชินี

Begin
   if all columns are filled, then
      return true
   for each row of the board, do
      if isValid(board, i, col), then
         set queen at place (i, col) in the board
         if solveNQueen(board, col+1) = true, then
            return true
         otherwise remove queen from place (i, col) from board.
   done
   return false
End

ตัวอย่าง

#include<iostream>
using namespace std;
#define N 8

void printBoard(int board[N][N]) {
   for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++)
         cout << board[i][j] << " ";
      cout << endl;
   }
}

bool isValid(int board[N][N], int row, int col) {
   for (int i = 0; i < col; i++)    //check whether there is queen in the left or not
      if (board[row][i])
         return false;
   for (int i=row, j=col; i>=0 && j>=0; i--, j--)
      if (board[i][j])       //check whether there is queen in the left upper diagonal or not
         return false;
   for (int i=row, j=col; j>=0 && i<N; i++, j--)
      if (board[i][j])      //check whether there is queen in the left lower diagonal or not
         return false;
   return true;
}

bool solveNQueen(int board[N][N], int col) {
   if (col >= N)           //when N queens are placed successfully
      return true;
   for (int i = 0; i < N; i++) {     //for each row, check placing of queen is possible or not
      if (isValid(board, i, col) ) {
         board[i][col] = 1;      //if validate, place the queen at place (i, col)
         if ( solveNQueen(board, col + 1))    //Go for the other columns recursively
            return true;
                   
         board[i][col] = 0;        //When no place is vacant remove that queen
      }
   }
   return false;       //when no possible order is found
}

bool checkSolution() {
   int board[N][N];
   for(int i = 0; i<N; i++)
      for(int j = 0; j<N; j++)
         board[i][j] = 0;      //set all elements to 0
               
   if ( solveNQueen(board, 0) == false ) {     //starting from 0th column
      cout << "Solution does not exist";
      return false;
   }
   printBoard(board);
   return true;
}

int main() {
   checkSolution();
}

ผลลัพธ์

1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0