Sudoku (DFS)

Original link

Sudoku is a traditional puzzle game , You need to put one $$\begin{gathered} 9 \\ times9 \end{gathered}$$ Sudoku complete , Make every line in Sudoku 、 Each column 、 Every $$\begin{gathered} 3 \\ times3 \end{gathered}$$ The number in the nine house grid $$\begin{gathered} 1 \\ sim9 \end{gathered}$$ All happen to happen once .

Please write a program to fill in Sudoku .

Input format

The input contains multiple sets of test cases .

One line per test case , contain $81$ Characters , Sudoku $81$ In cell data （ The overall order is from top to bottom , Walk from left to right ）.

Every character is a number （$1-9$） Or a .（ Indicates that... Has not been filled ）.

You can assume that each puzzle in the input has only one solution .

The end of the file contains the word end One way , End of input .

Output format

Each test case , Output a row of data , It represents Sudoku after complete filling .

sample input ：

4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end

sample output ：

417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936

---

Algorithm

(dfs)

Pruning and optimization ：

• Bit operation optimization ： In this question , Bit operation can quickly help us judge a row , Column , Whether there is a same number in the palace .

• Feasibility pruning ： Let's take a look at this grid and fill it here , Is it in your line , Column , There was no such thing in the palace .

• Optimal pruning ： We can choose an empty grid at will . Suppose we enumerate two lattices , There is a grid with 99 Seed filling method , There are two ways to fill a grid , Then we should first choose the one with less filling method

---

And here dfs use bool The advantage of type A is that you can find a solution all the way return fall

C++ Code

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 9,M = 1 << N;
int ones[M],map[M];// Respectively represent how many  1  Sum table array  
int row[N],col[N],cell[3][3];
char str[N * N];

#define lowbit(x) (x & -x) 
void init()//  initialization ( Initialize all positions to the status that can be filled )
{
    for (int i = 0;i < N;i ++ ) row[i] = col[i] = (1 << N) - 1;
    for (int i = 0;i < 3;i ++ ) 
        for (int j = 0;j < 3;j ++ ) 
            cell[i][j] = (1 << N) - 1;//  Every 3 * 3 The small squares of are also optimized with binary ( At first, it was also 1)
}
void draw(int x,int y,int t,bool is_set) //  stay (x, y) Location (is_set)< yes / no > fill t The operation of  
{
    if (is_set) str[x * N + y] = t + '1';
    else str[x * N + y] = '.';
    
    int v = 1 << t;//  Find the number corresponding to the position after the binary 
    if (!is_set) v = -v;// If you don't fill in, add it back , To keep it as it is 
    row[x] -= v;
    col[y] -= v;
    cell[x / 3][y / 3] -= v;
}
int get(int x,int y)
{
    return row[x] & col[y] & cell[x / 3][y / 3];
}
bool dfs(int u)
{
    if (!u) return true;
    int x,y,minv = 10;// x, y Record the location of the least enumeration scheme x, y, Record the current minimum enumeration scheme 

    for (int i = 0;i < N;i ++ ) {
        for (int j = 0;j < N;j ++ ) {
            if (str[i * N + j] == '.') {
                int state = get(i,j);//  Find the status of the number that can be filled in this position 
                if (ones[state] < minv) {
                    x = i,y = j;
                    minv = ones[state];
                }
            }
        }
    }
    int state = get(x,y);//  Find the status of the number that can be filled in the position corresponding to the least enumeration scheme 
    for (int i = state;i;i -= lowbit(i)) {
        int t = map[lowbit(i)];
        draw(x,y,t,true);//  Find the number that can be filled in this position 
        if (dfs(u - 1)) return true; //  If you find a set of feasible solutions, go all the way return true down 
        draw(x,y,t,false);
    }
    return false;
}
int main()
{
    for (int i = 0;i < N;i ++ ) map[1 << i] = i;// Preprocess the number of each base two 
    for (int i = 0;i < 1 << N;i ++ ) {
        for (int j = 0;j < N;j ++ ) {
            ones[i] += i >> j & 1;// How many binary representations of each number 1
        }
    }

    while (cin >> str && str[0] != 'e') {
        init();

        int cnt = 0;//  There are several blanks to fill in the record 
        for (int i = 0,k = 0;i < N;i ++ ) {
            for (int j = 0;j < N;j ++,k ++ ) {
                if (str[k] != '.') {// There is no need to fill in the number 
                    int t = str[k] - '1';
                    draw(i,j,t,true);
                }else cnt ++;
            }
        }
        dfs(cnt);
        puts(str);
    }
    return 0;
}