POJ3074 Sudoku(lowbit优化搜索)

In the game of Sudoku, you are given a large 9 × 9 grid divided into smaller 3 × 3 subgrids. For example,

. 2 7 3 8 . . 1 .

. 1 . . . 6 7 3 5

. . . . . . . 2 9

3 . 5 6 9 2 . 8 .

. . . . . . . . .

. 6 . 1 7 3 5 . 3

6 4 . . . . . . .

9 5 1 8 . . . 7 .

. 8 . . 6 5 3 4 .

Given some of the numbers in the grid, your goal is to determine the remaining numbers such that the numbers 1 through 9 appear exactly once in (1) each of nine 3 × 3 subgrids, (2) each of the nine rows, and (3) each of the nine columns.

输入

The input test file will contain multiple cases. Each test case consists of a single line containing 81 characters, which represent the 81 squares of the Sudoku grid, given one row at a time. Each character is either a digit (from 1 to 9) or a period (used to indicate an unfilled square). You may assume that each puzzle in the input will have exactly one solution. The end-of-file is denoted by a single line containing the word “end”.

输出

For each test case, print a line representing the completed Sudoku puzzle.

样例输入

.2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534.

......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.

end

样例输出

527389416819426735436751829375692184194538267268174593643217958951843672782965341

416837529982465371735129468571298643293746185864351297647913852359682714128574936

来源

Stanford Local 2006

题解：

这里使用了lowbit来优化当前的方案，存入二进制数后可以用Lowbit搜索每一位。

所以这说不定就是除了某d开头算法外数独较快的解法了吧。

#include <bits/stdc++.h>

#define lowbit(x) (x & (-x))

using namespace std;

char ch[12][12];

int hang[12], lie[12], gong[12], cnt[1200], num[1200], tot;

int get(int x, int y) { return (x / 3) * 3 + y / 3; }

void flip(int x, int y, int z) {

    hang[x] ^= (1 << z);

    lie[y] ^= (1 << z);

    gong[get(x, y)] ^= (1 << z);

    return;

}

bool dfs(int now) {

    if (!now)

        return 1;

    int mn = 10, x, y;

    for (int i = 0; i < 9; i++)

        for (int j = 0; j < 9; j++) {

            if (ch[i][j] != '.')

                continue;

            int val = hang[i] & lie[j] & gong[get(i, j)];

            if (!val)

                return 0; //矛盾，回退

            if (cnt[val] < mn) {

                mn = cnt[val];

                x = i, y = j;

            }

        }

    int val = hang[x] & lie[y] & gong[get(x, y)];

    for (int i = val; i; i -= lowbit(i)) {

        int which = num[lowbit(i)];

        ch[x][y] = '1' + which;

        flip(x, y, which);

        if (dfs(now - 1))

            return 1;

        flip(x, y, which);

        ch[x][y] = '.';

    }

    return 0;

}

char yyh[12000];

signed main() {

    for (int i = 0; i < (1 << 9); i++)

        for (int j = i; j; j -= lowbit(j))

            cnt[i]++; //有几个1

    for (int i = 0; i < 9; i++)

        num[1 << i] = i;

    while (scanf("%s", yyh) && yyh[0] != 'e') {

        for (int i = 0; i < 9; i++)

            for (int j = 0; j < 9; j++)

                ch[i][j] = yyh[i * 9 + j];

        for(int i=0;i<9;i++) hang[i]=lie[i]=gong[i]=(1<<9)-1;

        tot=0;

        for (int i = 0; i < 9; i++)

            for (int j = 0; j < 9; j++)

                if (ch[i][j]!='.') flip(i,j,ch[i][j]-'1');

                else tot++;

        dfs(tot);

        for(int i=0;i<9;i++) for(int j=0;j<9;j++) cout<<ch[i][j];

        puts("");

    }

    return 0;

}

巴特西

POJ3074 Sudoku(lowbit优化搜索)

最新文章

热门文章