സുഡോകു സോൾവർ


വൈഷമ്യ നില ഹാർഡ്
പതിവായി ചോദിക്കുന്നു ആമസോൺ ആപ്പിൾ ഡോർഡാഷ് ഗൂഗിൾ Intuit ജെപി മോർഗൻ മൈക്രോസോഫ്റ്റ് ഒറാക്കിൾ
ബാക്ക്ട്രാക്കിംഗ് ഹാഷ് ഹാഷിംഗ്

ഭാഗികമായി പൂരിപ്പിച്ച (9 x 9) സുഡോകു നൽകിയ സുഡോകു സോൾവർ പ്രശ്‌നത്തിൽ, പസിൽ പൂർത്തിയാക്കാൻ ഒരു പ്രോഗ്രാം എഴുതുക.

സുഡോകു ഇനിപ്പറയുന്ന സവിശേഷതകൾ പാലിക്കണം,

  1. ഓരോ സംഖ്യയും (1-9) ഒരു വരിയിൽ ഒരു തവണയും ഒരു നിരയിലും ഒരിക്കൽ പ്രത്യക്ഷപ്പെടണം.
  2. ഓരോ നമ്പറും (1-9) ഗ്രിഡിന്റെ ഒരു (3 x 3) ഉപ ബോക്സിൽ കൃത്യമായി ഒരിക്കൽ പ്രത്യക്ഷപ്പെടണം.

0 ഒരു ശൂന്യ സെല്ലിനെ പ്രതിനിധീകരിക്കുന്നു.

ഉദാഹരണം

ഇൻപുട്ട്:

സുഡോകു സോൾവർ

ഔട്ട്പുട്ട്:

അൽഗോരിതം

അടിസ്ഥാനം അൽഗോരിതം സുഡോകു പസിൽ (സുഡോകു സോൾവർ) പരിഹരിക്കുക എന്നത് അക്കങ്ങളുടെ എല്ലാ കോമ്പിനേഷനുകളും പരീക്ഷിച്ച് മുകളിലുള്ള വ്യവസ്ഥകളെ തൃപ്തിപ്പെടുത്തുന്ന പരിഹാരം തിരഞ്ഞെടുക്കുക എന്നതാണ്.

ഈ പ്രക്രിയയുടെ സമയ സങ്കീർ‌ണ്ണത വളരെ ഉയർന്നതാണ്, അതിനാൽ‌ നിലവിലെ പാത ഒരു പരിഹാരത്തിലേക്ക് നയിക്കില്ലെന്ന് ഞങ്ങൾ‌ കണ്ടെത്തിയയുടനെ ആവർത്തനം കുറയ്‌ക്കാൻ ഞങ്ങൾ‌ ബാക്ക്‌ട്രാക്കിംഗ് ഉപയോഗിക്കുന്നു.

ഇത് പസിൽ പരിഹരിക്കുന്നതിന് എടുക്കുന്ന സമയം കുറയ്ക്കുന്ന പ്രവണത കാണിക്കുന്നു, പക്ഷേ സമയ സങ്കീർണ്ണതയുടെ മൊത്തത്തിലുള്ള പരിധി അതേപടി തുടരുന്നു.

  1. ഒരു ശൂന്യമായ സെൽ കണ്ടെത്തുക, ശൂന്യമായ സെൽ ഇല്ലെങ്കിൽ, പസിൽ പരിഹരിച്ച് ഞങ്ങൾ മടങ്ങും.
  2. ശൂന്യമായ സെല്ലിന്റെ വരിയും നിരയും യഥാക്രമം i, j ആയിരിക്കട്ടെ.
  3. ശൂന്യമായ സെല്ലിലേക്ക് ഓരോന്നായി നമ്പറുകൾ നൽകുക, ഒരു നമ്പർ നൽകുന്നത് സുരക്ഷിതമാണെങ്കിൽ, മുകളിലുള്ള ഘട്ടങ്ങൾ ആവർത്തിച്ച് ആവർത്തിക്കുക.
  4. ഈ അസൈൻ‌മെന്റ് ഒരു പരിഹാരത്തിലേക്ക് നയിക്കുകയാണെങ്കിൽ‌, ശരിയിലേക്ക് മടങ്ങുക.
  5. നിലവിലെ ശൂന്യമായ സെല്ലിനായി അടുത്ത നമ്പർ ശ്രമിക്കുക.

അസൈൻ‌മെന്റ് സുരക്ഷിതമാണോ അല്ലയോ എന്ന് പരിശോധിക്കുന്നു,
ഒരു സെല്ലിൽ ഒരു നമ്പർ സാധുതയുള്ളതാകാൻ, അത് സുഡോകു പസിലിന്റെ അടിസ്ഥാന സവിശേഷതകൾ പാലിക്കണം (മുകളിൽ വിവരിച്ചിരിക്കുന്നത്).

  1. നിയുക്ത നമ്പർ നിലവിലെ വരിയിലോ നിലവിലെ നിരയിലോ ഉണ്ടെങ്കിൽ, തെറ്റായി മടങ്ങുക.
  2. ശൂന്യമായ സെൽ ഉള്ള 3 × 3 ഉപ ബോക്സിന്റെ വരിയുടെയും നിരയുടെയും ആരംഭ സൂചിക കണക്കാക്കുക.
  3. നിയുക്ത നമ്പർ നിലവിലെ 3 × 3 ഉപ ബോക്സിൽ ഉണ്ടെങ്കിൽ, തെറ്റായി മടങ്ങുക.
  4. ശരിയിലേക്ക് മടങ്ങുക.

സുഡോകു സോൾവറിനായുള്ള സ്യൂഡോ കോഡ്

// സുഡോകു പസിൽ പരിഹരിക്കാനുള്ള പ്രവർത്തനം
പരിഹരിക്കുക (സുഡോകു)

// Find an empty cell
int i = 0, j = 0
for (int i = 0; i < 9; i++) {
  for (int j = 0; j < 9; j++) {
    if (sudoku[i][j] == 0)
      break
  }
}
// No empty cell found
if (i == 9 && j == 9)
  return true
// Try all the numbers one by one
for (int n = 1; n <= 9; n++) {
  // If the assignment is valid
  if (isSafe(sudoku, i, j, n)) {
    // Assign the value to this cell
    sudoku[i][j] = n
    // If recursion leads to a solution, return true
    if (solve(sudoku))
      return true
    // Back tracking
    sudoku[i][j] = 0
  }
}

// നൽകിയ സെല്ലിലെ ഒരു സംഖ്യയുടെ സാധുത പരിശോധിക്കുന്നതിനുള്ള പ്രവർത്തനം
isSafe (സുഡോകു, i, j, n)

// Check in current row and column
for (int x = 0; x < 9; x++)
  if (sudoku[i][x] == n || sudoku[x][j] == n)
    return false
// Calculate starting index of row and column of 3 x 3 sub box
int rs = i - (i % 3)
int cs = j - (j % 3)
// Check in 3 x 3 sub box
for (int x = 0; x < 3; x++) 
  for (int y = 0; y < 3; y++)
    if (sudoku[x + rs][y + cs] == n)
      return false
return true

ജാവ കോഡ്

public class SudokoSolver {
    public static boolean solve(int[][] sudoku) {
        int i = 0, j = 0;
        boolean found = false;
        // Find an empty cell
        for (i = 0; i < 9; i++) {
            for (j = 0; j < 9; j++) {
                if (sudoku[i][j] == 0) {
                    found = true;
                    break;
                }
            }
            if (found) {
                break;
            }
        }

        // No empty cell found, return true
        if (i == 9 && j == 9) {
            return true;
        }

        // One by one try all the values in the current cell
        for (int n = 1; n <= 9; n++) {
            // check if it is valid to assign value n to current cell
            if (isSafe(i, j, n, sudoku)) {
                sudoku[i][j] = n;
                // Recursively solve the sudoku
                if (solve(sudoku)) {
                    return true;
                }
                // back track if the recursion returns false
                sudoku[i][j] = 0;
            }
        }
        
        // Return false if no value fits
        return false;
    }

    public static boolean isSafe(int i, int j, int n, int[][] sudoku) {
        // Check in current row and column
        for (int x = 0; x < 9; x++) {
            // Row
            if (sudoku[i][x] == n) {
                return false;
            }
            // Column
            if (sudoku[x][j] == n) {
                return false;
            }
        }
        
        // Calculate the starting index of row and column of current 3x3 sub box
        int rs = i - (i % 3);
        int cs = j - (j % 3);

        // Check in the current sub box
        for (int x = 0; x < 3; x++) {
            for (int y = 0; y < 3; y++) {
                if (sudoku[x + rs][y + cs] == n) {
                    return false;
                }
            }
        }

        // Return true
        return true;
    }

    public static void main(String[] args) {
        // Partially filled sudoku puzzle
        int[][] sudoko = new int[][] {
                {5, 3, 0, 0, 7, 0, 0, 0, 0},
                {6, 0, 0, 1, 9, 5, 0, 0, 0},
                {0, 9, 8, 0, 0, 0, 0, 6, 0},
                {8, 0, 0, 0, 6, 0, 0, 0, 3},
                {4, 0, 0, 8, 0, 3, 0, 0, 1},
                {7, 0, 0, 0, 2, 0, 0, 0, 6},
                {0, 6, 0, 0, 0, 0, 2, 8, 0},
                {0, 0, 0, 4, 1, 9, 0, 0, 5},
                {0, 0, 0, 0, 8, 0, 0, 7, 9}
        };

        solve(sudoko);

        // Print the answer
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(sudoko[i][j] + " ");
            }
            System.out.println();
        }
    }
}

സുഡോകു സോൾവറിനായുള്ള സി ++ കോഡ്

#include <bits/stdc++.h>
using namespace std;

bool isSafe(vector<vector<int>> &sudoku, int i, int j, int n) {
    // Check in current row and column
    for (int x = 0; x < 9; x++) {
        // Row
        if (sudoku[i][x] == n) {
            return false;
        }
        // Column
        if (sudoku[x][j] == n) {
            return false;
        }
    }
    
    // Calculate the starting index of row and column of current 3x3 sub box
    int rs = i - (i % 3);
    int cs = j - (j % 3);

    // Check in the current sub box
    for (int x = 0; x < 3; x++) {
        for (int y = 0; y < 3; y++) {
            if (sudoku[x + rs][y + cs] == n) {
                return false;
            }
        }
    }

    // Return true
    return true;
}

bool solve(vector<vector<int>> &sudoku) {
    int i = 0, j = 0;
    bool found = false;
    // Find an empty cell
    for (i = 0; i < 9; i++) {
        for (j = 0; j < 9; j++) {
            if (sudoku[i][j] == 0) {
                found = true;
                break;
            }
        }
        if (found)
            break;
    }
    
    // No empty cell found, return true
    if (i == 9 && j == 9) {
        return true;
    }
    
    // One by one try all the values in the current cell
    for (int n = 1; n <= 9; n++) {
        // check if it is valid to assign value n to current cell
        if (isSafe(sudoku, i, j, n)) {
            sudoku[i][j] = n;
            // Recursively solve the sudoku
            if (solve(sudoku) == true)
                return true;
            // back track if the recursion returns false
            sudoku[i][j] = 0;
        }
    }
    
    // Return false if no value fits
    return false;
}

int main() {
    // Partially filled sudoku puzzle
    vector<vector<int>> sudoku =  {
                {5, 3, 0, 0, 7, 0, 0, 0, 0},
                {6, 0, 0, 1, 9, 5, 0, 0, 0},
                {0, 9, 8, 0, 0, 0, 0, 6, 0},
                {8, 0, 0, 0, 6, 0, 0, 0, 3},
                {4, 0, 0, 8, 0, 3, 0, 0, 1},
                {7, 0, 0, 0, 2, 0, 0, 0, 6},
                {0, 6, 0, 0, 0, 0, 2, 8, 0},
                {0, 0, 0, 4, 1, 9, 0, 0, 5},
                {0, 0, 0, 0, 8, 0, 0, 7, 9}
    };
        
    solve(sudoku);

    // Print the answer
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cout<<sudoku[i][j]<<" ";
        }
        cout<<endl;
    }
    
    return 0;
}
5 3 4 6 7 8 9 1 2 
6 7 2 1 9 5 3 4 8 
1 9 8 3 4 2 5 6 7 
8 5 9 7 6 1 4 2 3 
4 2 6 8 5 3 7 9 1 
7 1 3 9 2 4 8 5 6 
9 6 1 5 3 7 2 8 4 
2 8 7 4 1 9 6 3 5 
3 4 5 2 8 6 1 7 9 

സുഡോകു സോൾവറിനായുള്ള സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (9 ^ (n * n)): നിയുക്തമാക്കാത്ത ഓരോ സൂചികയ്ക്കും 9 സാധ്യമായ ഓപ്ഷനുകൾ ഉണ്ട്, അതിനാൽ സുഡോകു സോൾവറിന്റെ ഏറ്റവും മോശം സമയ സങ്കീർണ്ണത O (9 ^ (n * n)) ആണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

 O (n * n): Ar ട്ട്‌പുട്ട് അറേ സംഭരിക്കുന്നതിന് ഒരു മാട്രിക്സ് ആവശ്യമാണ്.

അവലംബം