सुडोकू सॉल्विंग एल्गोरिदम

इस खंड में, हम प्रसिद्ध नंबर मेज़ समस्या जिसे सुडोकू कहा जाता है, को हल करने का प्रयास करेंगे। सुडोकू एक 9 x 9 नंबर ग्रिड है, और पूरा ग्रिड 3 x 3 बॉक्स में भी विभाजित है। सुडोकू हल करने के लिए कुछ नियम हैं।

हमें इस समस्या को हल करने के लिए 1 से 9 तक के अंकों का उपयोग करना होगा।

एक अंक को एक पंक्ति, एक कॉलम या एक 3 x 3 बॉक्स में दोहराया नहीं जा सकता।

बैकट्रैकिंग एल्गोरिदम का उपयोग करके, हम सुडोकू समस्या को हल करने का प्रयास करेंगे। जब किसी सेल को एक अंक से भरा जाता है, तो यह जांचता है कि यह वैध है या नहीं। जब यह वैध नहीं होता, तो यह अन्य नंबरों की जांच करता है। यदि 1-9 से सभी नंबर चेक किए गए हैं, और रखने के लिए कोई वैध अंक नहीं मिला, तो यह पिछले विकल्प पर बैकट्रैक करता है।

इनपुट और आउटपुट

इनपुट: यह 9 x 9 मैट्रिक्स को सुडोकू ग्रिड के रूप में लेगा। कुछ मान ग्रिड में रखे गए हैं। खाली स्थानों को 0 से दर्शाया गया है।  आउटपुट: अंतिम मैट्रिक्स (सुडोकू ग्रिड) संख्याओं से भरा हुआ। यदि समाधान मौजूद नहीं है, तो यह 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)

इनपुट: कॉलम, और लक्षित संख्या

आउटपुट - जब दी गई कॉलम में संख्या मौजूद हो तो True

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

isPresentInRow(row, num)

इनपुट - पंक्ति, और लक्षित संख्या

आउटपुट - जब दी गई कॉलम में संख्या मौजूद हो तो True

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 बॉक्स की शुरुआती पंक्ति और कॉलम, और लक्षित संख्या

आउटपुट - जब बॉक्स में संख्या मौजूद हो तो True

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(row, col)

इनपुट: ग्रिड में पंक्ति और कॉलम

आउटपुट - यदि grid[row, col] खाली है, तो true वापस करें, अन्यथा false

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(row, col, num)

इनपुट: ग्रिड की पंक्ति, एक कॉलम, और जांचने के लिए संख्या

आउटपुट: True, जब संख्या को grid[row, 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

solveSudoku(Sudoku Grid)

इनपुट: सुडोकू का अनसुलझा ग्रिड

आउटपुट: हल करने के बाद ग्रिड

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  #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

आउटपुट
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