C++で部分的に満たされた数独グリッドを解決するためのプログラム

部分的に塗りつぶされた数独グリッドがあり、これを解決する必要があるとします。数独は9×9の数字グリッドであり、グリッド全体も3×3のボックスに分割されていることがわかっています。数独を解決するためのルールがいくつかあります。

• この問題を解決するには、1から9までの数字を使用する必要があります。

• 1行、1列、または1つの3×3ボックスで1桁を繰り返すことはできません。

バックトラッキングアルゴリズムを使用して、数独問題の解決を試みます。一部のセルが数字で埋められると、それが有効かどうかをチェックします。無効な場合は、他の番号をチェックします。すべての数字が1〜9でチェックされ、有効な数字が見つからない場合は、前のオプションに戻ります。

したがって、入力が-

出力は-

これを解決するには、次の手順に従います-

• isPresentInCol（）というメソッドを定義します。これには、呼び出しとnumが必要です

• グリッドの各行rについて、実行します

  • grid [r、col] =numの場合、trueを返します

• それ以外の場合はfalseを返します

• isPresentInRow（）というメソッドを定義します。これは行と数値を取ります

• グリッドの各列cについて、次のようにします

  • grid [row、c] =numの場合、trueを返します

• それ以外の場合はfalseを返します

• isPresentInBox（）というメソッドを定義します。これは、boxStartRow、boxStartCol、num

  を取ります。

• boxStartRowの各行rから次の3行まで、実行します

  • boxStartColの次の3列までの各列について、実行します

    • grid [r、c] =numの場合、trueを返します

• それ以外の場合はfalseを返します

• findEmptyPlace（）というメソッドを定義します。これは行と列を取ります

• グリッドの各行rについて、実行します

  • グリッドの各列cについて、次のようにします

    • grid [r、c] =0の場合、trueを返します

• falseを返す

• isValidPlace（）というメソッドを定義します。これには、row、col、num

  が必要です。

• isPresentInRow（row、num）およびisPresentInCol（col、num）およびisPresntInBox（row − row mod 3、col − col mod 3、num）がすべてfalseの場合、trueを返します

• SolveSudoku（）というメソッドを定義します。これにより、グリッドが使用されます

• グリッド内に空の場所がない場合は、trueを返します

• 1から9までは、

  • isValidPlace（row、col、number）の場合、

    • grid [row、col]：=number

    • SolveSudoku =trueの場合、trueを返します

    • grid [row、col]：=0

• falseを返す

理解を深めるために、次の実装を見てみましょう-

例

#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) &&
   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) &&
   cout << "No solution exists";
}

入力

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

出力

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