Summary of main ideas of JavaScript traversal in solving Sudoku problem

  • 2021-06-28 10:35:25
  • OfStack

Sudoku Rule
Sudoku game, classic 9×9 = 81 cells in a 9-cell grid, which also forms 3×3 = 9 small 9 panes, requiring numbers 1-9 to be filled in 81 small cells, and numbers cannot be repeated in each row, column, or in each small 9 pane.

Sudoku Strategies

Visual method Candidates Elimination Techniques Relevant 210 bins: A number is only related to 210 bins in its row and column and small 9 bins

My thoughts

A well-designed validity evaluation function is designed, and a maximum of 81 small cells can be traversed once to make a validity evaluation of the scheme. Similarly, 20 lattice judgments are designed, and a 0-9 cycle is used to complete the validity judgment. Simulate the stack with an array to provide backtracking information for the search. Using the map property of the object to help judge the validity of the scheme, the algorithm is greatly simplified.

Scheme Design and Implementation
Only one 2-dimensional array was used to store the Sudoku scheme, one 1-dimensional array as the stack, and one Boolean variable as the backtrace identifier.

1. Variable Definition:


var problem = [        // This is the difficulty mentioned in the book 10.7 Title of 
  [8,0,0,0,0,0,0,0,0],
  [0,0,3,6,0,0,0,0,0],
  [0,7,0,0,9,0,2,0,0],
  [0,5,0,0,0,7,0,0,0],
  [0,0,0,0,4,5,7,0,0],
  [0,0,0,1,0,0,0,3,0],
  [0,0,1,0,0,0,0,6,8],
  [0,0,8,5,0,0,0,1,0],
  [0,9,0,0,0,0,4,0,0]
]
var stack = [],flag = false;

2. Scheme validity determination:
Making full use of the hash feature of the javascript object, for debugging convenience, the return value of the function is 0 when it is valid and 3 when it is invalid. Row conflict, column conflict and small 9-grid conflict return 1, 2, 3 respectively.Previous judgment used it, and later added the relevant 210-grid judgment, this function will not be used when finding the answer.


function checkValid(sudo){
  let subSudo = {}            // Auxiliary variable to determine small 9 Is the palace in conflict 
  for(let i = 0; i<9; i++){
    let row = {}, col = {}       // Auxiliary variable to determine whether rows and columns conflict 
    for(let j = 0; j<9; j++){
      let cur1 = sudo[i][j], cur2 = sudo[j][i]      //1 Decision of Row and Column Completed Simultaneously by Secondary Inner Loop 
      if(row[cur1])          // The current element has already appeared in the row, optimizing the zero drop judgment, key by 0 Time value is 0 , no extra judgment is required 
        return 1;          // Return error code 
      else
        row[cur1] = cur1      // The current element does not appear in a row and is stored in an auxiliary variable   
      if(col[cur2])          // Column decisions are similar to rows, optimizing zero-dropping decisions. key by 0 Time value is 0 , no extra judgment is required 
        return 2;
      else
        col[cur2] = cur2;
      let key = Math.floor(i/3)+'-'+Math.floor(j/3)    // For different small 9 The generation of palaces is different key
      if(subSudo[key]){         // Small 9 There are already elements in the palace, optimizing the zero-dropping judgment, key by 0 Time value is 0 , no extra judgment is required 
        if(subSudo[key][cur1])    // To 1 Small 9 The palace's decision is similar to the row's 
          return 3
        else
          subSudo[key][cur1] = cur1
      }else{              // This is a small 9 In the palace 1 Elements 
        subSudo[key] = {}       // For small 9 New Palace 1 And 1 Elements stored in 
        subSudo[key][cur1] = cur1
      }         
    }
  }
  return 0;                // The program runs here, indicating that the scheme is valid 
}

3. Relevant 210-grid decision
The principle is the same as the overall judgment, and the highlight is on the positioning of the small 9 palaces.

function check20Grid(sudo,i,j){        
  let row = {}, col = {}, subSudo = {}        // Auxiliary variable 
  for(let k = 0; k < 9; k++){
    let cur1 = sudo[i][k], cur2 = sudo[k][j]
    if(cur1){                    // The current element has already appeared in the row, optimizing the zero drop judgment, key by 0 Time value is 0 , no extra judgment is required 
      if(row[cur1])
        return 1;                // Return error code 
      else
        row[cur1] = cur1            // The current element does not appear in a row and is stored in an auxiliary variable 
    }
    if(cur2){                    // Column decisions are similar to rows, optimizing zero-dropping decisions. key by 0 Time value is 0 , no extra judgment is required 
      if(col[cur2])
        return 2;
      else
        col[cur2] = cur2;
    }
    // Convert Loop Variable to Small 9 Coordinates of the palace 
    let key = sudo[Math.floor(i/3)*3 + Math.floor(k/3)][Math.floor(j/3)*3+Math.floor(k%3)]
    if(subSudo[key])                //9 The palace judgement is similar to the row, optimizing the zero-dropping judgement. key by 0 Time value is 0 , no extra judgment is required 
      return 3
    else
      subSudo[key] = key
  }
  return 0;
}

4. Traversal Solution
An element with zero initial state is a pending feature, and with the help of the stack, no additional storage space is created.


function findAnswer(){
  for(let i = 0; i<9; i++){
    for(let j = 0; j<9; ){
      if(problem[i][j] === 0 || flag){       // The current position is the first processing or backtracking of the element to be determined. The two situations seem different, but they are actually the same. 1 that will do 
        flag = false;
        let k = problem[i][j] + 1;        // Search Down 1 Legitimate value advances 
        while(k<10){               // Loop Find Down 1 Legal values 
          problem[i][j] = k;          // Fill-in Value 
          if(check20Grid(problem,i,j) == 0){  // Adjudicate legitimate, relevant 210 Lattice determination 
            stack.push([i,j++])        // Store backtracking points and step by step 
            break;
          }
          k++;
        }
        if(k>9){                 // No legal value found at current location, backtracking 
          problem[i][j] = 0;          // Return to zero before backtracking 
          let rt = stack.pop();         // Retrieving backtrace information from stack 
          if(!rt)                // No solution, go back 0
            return 0;  
          i=rt[0]                // Pass through 
          j=rt[1]
          flag = true;
        }
      }else{                    // Current position number given for title 
        j++;
      }
    }
  }
  return 1;                      // Successfully found 1 Configuration 
}


Related articles: