อัลกอริทึมการแก้ซูโดกุ

ในส่วนนี้ เราจะพยายามแก้ปัญหาเขาวงกตตัวเลขที่มีชื่อเสียงที่เรียกว่าซูโดกุ ซูโดกุเป็นตารางตัวเลข 9 x 9 และทั้งตารางยังถูกแบ่งออกเป็นกล่อง 3 x 3 มีกฎบางอย่างในการแก้ซูโดกุ

เราต้องใช้ตัวเลข 1 ถึง 9 เพื่อแก้ปัญหานี้

ไม่สามารถทำซ้ำหนึ่งหลักในหนึ่งแถว หนึ่งคอลัมน์ หรือในกล่อง 3 x 3 หนึ่งช่อง

เราจะพยายามแก้ปัญหาซูโดกุโดยใช้อัลกอริธึมย้อนรอย เมื่อเติมตัวเลขลงในเซลล์บางเซลล์ ระบบจะตรวจสอบว่าถูกต้องหรือไม่ เมื่อไม่ถูกต้องจะตรวจสอบหมายเลขอื่น หากตรวจสอบหมายเลขทั้งหมดตั้งแต่ 1-9 และไม่พบตัวเลขที่ถูกต้อง ให้ย้อนกลับไปที่ตัวเลือกก่อนหน้า

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

Input:
This will take a 9 x 9 matrix as Sudoku grid. Some values are placed in the grid. The blank spaces are denoted by 0.

Output:
The final matrix (Sudoku grid) filled with numbers. If the solution does not exist, it will return false.

3 1 6  | 5 7 8  | 4 9 2
5 2 9  | 1 3 4  | 7 6 8
4 8 7  | 6 2 9  | 5 3 1
------------------------
2 6 3  | 4 1 5  | 9 8 7
9 7 4  | 8 6 3  | 1 2 5
8 5 1  | 7 9 2  | 6 4 3
------------------------
1 3 8  | 9 4 7  | 2 5 6
6 9 2  | 3 5 1  | 8 7 4
7 4 5  | 2 8 6  | 3 1 9    

อัลกอริทึม

isPresentInCol(col, num)

อินพุต: คอลัมน์และหมายเลขเป้าหมาย

ผลลัพธ์ − เป็นจริงเมื่อตัวเลขอยู่ในคอลัมน์ที่กำหนด

Begin
   for each row r in the grid, do
      if grid[r, col] = num, then
         return true
   done
   return false otherwise
End

isPresentInRow(แถว หมายเลข)

ป้อนข้อมูล - แถวและหมายเลขเป้าหมาย

ผลลัพธ์ − เป็นจริงเมื่อตัวเลขอยู่ในคอลัมน์ที่กำหนด

Begin
   for each column c in the grid, do
      if grid[row, c] = num, then
         return true
   done
   return false otherwise
End

isPresentInBox(boxStartRow, boxStartCol, num)

ป้อนข้อมูล - แถวและคอลัมน์เริ่มต้นของช่อง 3 x 3 และตัวเลขเป้าหมาย

ผลลัพธ์ − เป็นจริงเมื่อตัวเลขอยู่ในช่อง

Begin
   for each row r in boxStartRow to next 3 rows, do
      for each col r in boxStartCol to next 3 columns, do
         if grid[r, c] = num, then
            return true
      done
   done
   return false otherwise
End

findEmptyPlace(แถว, คอลัมน์)

ป้อนข้อมูล: แถวและคอลัมน์ในตาราง

ผลลัพธ์ − หาก grid[row, col] ว่างเปล่า ให้คืนค่า true ไม่เช่นนั้นจะเท็จ

Begin
   for each row r in the grid, do
      for each column c in the grid, do
         if grid[r, c] = 0, then
            return true
      done
   done
   return false
End

isValidPlace(แถว col num)

ป้อนข้อมูล: แถว คอลัมน์ของตาราง และตัวเลขที่จะตรวจสอบ

ผลลัพธ์: จริง เมื่อวางตัวเลขที่ตำแหน่งกริด[แถว, col] ถูกต้อง

Begin
   if isPresentInRow(row, num) and isPresentInCol(col, num) and
   isPresntInBox(row – row mod 3, col – col mod 3, num) all are false, then
      return true
End

แก้ซูโดกุ(ตารางซูโดกุ)

ป้อนข้อมูล: ตารางที่ยังไม่แก้ของซูโดกุ

ผลลัพธ์: กริดหลังจากแก้

Begin
   if no place in the grid is empty, then
      return true
   for number 1 to 9, do
      if isValidPlace(row, col, number), then
         grid[row, col] := number
         if solveSudoku = true, then
            return true
         grid[row, col] := 0
   done
   return false
End

ตัวอย่าง

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

int grid[N][N] = {
   {3, 0, 6, 5, 0, 8, 4, 0, 0},
   {5, 2, 0, 0, 0, 0, 0, 0, 0},
   {0, 8, 7, 0, 0, 0, 0, 3, 1},
   {0, 0, 3, 0, 1, 0, 0, 8, 0},
   {9, 0, 0, 8, 6, 3, 0, 0, 5},
   {0, 5, 0, 0, 9, 0, 6, 0, 0},
   {1, 3, 0, 0, 0, 0, 2, 5, 0},
   {0, 0, 0, 0, 0, 0, 0, 7, 4},
   {0, 0, 5, 2, 0, 6, 3, 0, 0}
};

bool isPresentInCol(int col, int num) {    //check whether num is present in col or not
   for (int row = 0; row < N; row++)
      if (grid[row][col] == num)
         return true;
   return false;
}

bool isPresentInRow(int row, int num) {    //check whether num is present in row or not
   for (int col = 0; col < N; col++)
      if (grid[row][col] == num)
         return true;
   return false;
}

bool isPresentInBox(int boxStartRow, int boxStartCol, int num) {    //check whether num is present in 3x3 box or not
   for (int row = 0; row < 3; row++)
      for (int col = 0; col < 3; col++)
         if (grid[row+boxStartRow][col+boxStartCol] == num)
            return true;
   return false;
}

void sudokuGrid() {    //print the sudoku grid after solve
   for (int row = 0; row < N; row++) {
      for (int col = 0; col < N; col++) {
         if(col == 3 || col == 6)
            cout << " | ";
         cout << grid[row][col] <<" ";
      }

      if(row == 2 || row == 5) {
         cout << endl;
         for(int i = 0; i<N; i++)
            cout << "---";
      }
      cout << endl;
   }
}

bool findEmptyPlace(int &row, int &col) {    //get empty location and update row and column
   for (row = 0; row < N; row++)
      for (col = 0; col < N; col++)
         if (grid[row][col] == 0) //marked with 0 is empty
            return true;
   return false;
}

bool isValidPlace(int row, int col, int num) {
   //when item not found in col, row and current 3x3 box
   return !isPresentInRow(row, num) && !isPresentInCol(col, num) && !isPresentInBox(row - row%3 , col - col%3, num);
}

bool solveSudoku() {
   int row, col;
   if (!findEmptyPlace(row, col))
      return true;     //when all places are filled
   for (int num = 1; num <= 9; num++) {     //valid numbers are 1 - 9
      if (isValidPlace(row, col, num)) {    //check validation, if yes, put the number in the grid
         grid[row][col] = num;
         if (solveSudoku())     //recursively go for other rooms in the grid
            return true;
         grid[row][col] = 0;    //turn to unassigned space when conditions are not satisfied
      }
   }
   return false;
}

int main() {
   if (solveSudoku() == true)
      sudokuGrid();
   else
      cout << "No solution exists";
}

ผลลัพธ์

3 1 6  | 5 7 8  | 4 9 2
5 2 9  | 1 3 4  | 7 6 8
4 8 7  | 6 2 9  | 5 3 1
------------------------
2 6 3  | 4 1 5  | 9 8 7
9 7 4  | 8 6 3  | 1 2 5
8 5 1  | 7 9 2  | 6 4 3
------------------------
1 3 8  | 9 4 7  | 2 5 6
6 9 2  | 3 5 1  | 8 7 4
7 4 5  | 2 8 6  | 3 1 9