Sudoku Solver_sudoku solver 16by16_The Lonely Square Root 13 Blog

class=”htmledit_views”>

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle…

… and its solution numbers marked in red.

1. My answer: Backtrack

Traverse each position, and use 1~9 to place this position, and check if the character does not match. It takes a lot of time, no reason, it may need to be optimized

//
 // main.cpp
 // sudo
 //
 // Created by zjl on 16/4/30.
 // Copyright 2016 zjl. All rights reserved.
 //
 #include 
 #include 
 using namespace std;
 bool judge(vector<vector> board, int r, int c, char target){
     for(int i = 0; i < 9; i++){
         if(board[r][i]==target || board[i][c]==target)
             return false;
     }
     int br = 3*(r/3), cr = 3*(c/3);
     for(int k = br; k < br+3; k++){
         for(int j = cr; j < cr+3; j++){
             if(board[k][j] == target)
                 return false;
         }
     }
     return true;
 }
 void print_vec(vector<vector> b){
     for(int p = 0; p < b. size(); p++){
         for(int q = 0; q < b[p].size(); q++){
             cout<<b[p][q]<<" ";
         }
         cout<<endl;
     }
 }
 bool Sudo(vector<vector>& board, int row, int col){
     bool b = false;
     if(board[row][col]!='.'){
         if(col+1 = 9 && row+1 < 9){
             b = sudo(board,row+1,0);
             if(b) return true;
         }else return true;//When the traversal reaches the last one, it will return true
         return false;
     }else{
     for(int i = 1; i <= 9; i++){
         if(judge(board,row,col,i+'0')){
             board[row][col] = i+'0';
             if(col+1 = 9 && row+1 < 9){
                 b = sudo(board,row+1,0);
                 if(b) return true;
                 else board[row][col] = '.';
             }
             else
                 return true;//When the last one is traversed, it will return true
         }
     }
       return false;
     }
   
 }
 void solveSudoku(vector<vector>& board) {
     int i = 0, j = 0, label = 0;
     bool b = Sudo(board,i,j);
 }
 int main(int argc, const char * argv[]) {
     vector<vector> board={
    {'.','.','9','7','4','8','.','.','.'},{'7','.','  .','.','.','.','.','.','.'},{'.','2','.','1','.','  9','.','.','.'},{'.','.','7','.','.','.','2','4','  .'},{'.','6','4','.','1','.','5','9','.'},{'.','9'  ,'8','.','.','.','3','.','.'},{'.','.','.','8','.'  ,'3','.','2','.'},{'.','.','.','.','.','.','.','.'  ,'6'},{'.','.','.','2','7','5','9','.','.'}};
     solveSudoku(board);
     print_vec(board);
     return 0;
 }
 

Output:

5 1 9 7 4 8 6 3 2

7 8 3 6 5 2 4 1 9

4 2 6 1 3 9 8 7 5

3 5 7 9 8 6 2 4 1

2 6 4 3 1 7 5 9 8

1 9 8 5 2 4 3 6 7

9 7 5 8 6 3 1 2 4

8 3 2 4 9 1 7 5 6

6 4 1 2 7 5 9 8 3