＜C/C++＞解数独

题目描述

问题描述：数独（Sudoku）是一款大众喜爱的数字逻辑游戏。玩家需要根据9X9盘面上的已知数字，推算出所有剩余空格的数字，并且满足每一行、每一列、每一个粗线宫内的数字均含1-9，并且不重复。

输入：

包含已知数字的9X9盘面数组[空缺位以数字0表示]

输出：

完整的9X9盘面数组

输入描述:

包含已知数字的9X9盘面数组[空缺位以数字0表示]

输出描述:

完整的9X9盘面数组

示例1
输入

0 9 2 4 8 1 7 6 3
4 1 3 7 6 2 9 8 5
8 6 7 3 5 9 4 1 2
6 2 4 1 9 5 3 7 8
7 5 9 8 4 3 1 2 6
1 3 8 6 2 7 5 9 4
2 7 1 5 3 8 6 4 9
3 8 6 9 1 4 2 5 7
0 4 5 2 7 6 8 3 1

输出

5 9 2 4 8 1 7 6 3
4 1 3 7 6 2 9 8 5
8 6 7 3 5 9 4 1 2
6 2 4 1 9 5 3 7 8
7 5 9 8 4 3 1 2 6
1 3 8 6 2 7 5 9 4
2 7 1 5 3 8 6 4 9
3 8 6 9 1 4 2 5 7
9 4 5 2 7 6 8 3 1

C++解法：

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

int sudoku[9][9];
vector<int> unknownIndices;

int toIndex(int index, int subIndex) {
    return (subIndex << 4) + index;
}

void parseSudoku(string line, int index) {
    int subIndex = 0;
    char single;
    for (int i = 0; i < line.length(); i++) {
        single = line.at(i);
        if (isdigit(single)) {
            if (single == '0') {
                unknownIndices.push_back(toIndex(index, subIndex));
            }
            sudoku[index][subIndex++] = single - '0';
        }
    }
}


const int lineTotal = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9;
bool figureOut(int index, int subIndex) {

    int total = 0;
    // 纵向
    for (int i = 0; i < 9; i++) {
        if (i == index) {
            continue;
        }
        total += sudoku[i][subIndex];
    }
    int offset = lineTotal - total;
    if (offset <= 9) {
        sudoku[index][subIndex] = offset;
        return true;
    }

    total = 0;
    // 横向
    for (int i = 0; i < 9; i++) {
        if (i == subIndex) {
            continue;
        }
        total += sudoku[index][i];
    }
    offset = lineTotal - total;
    if (offset <= 9) {
        sudoku[index][subIndex] = offset;
        return true;
    }

    total = 0;
    int rowStart = (index / 3) * 3;
    int colStart = (subIndex / 3) * 3;

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (i == index && j == subIndex) {
                continue;
            }
            total += sudoku[i+rowStart][j+colStart];
        }
    }
    offset = lineTotal - total;
    if (offset <= 9) {
        sudoku[index][subIndex] = offset;
        return true;
    }
    return false;
}

void printSudoku() {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cout << sudoku[i][j] << " ";
        }
        cout << endl;
    }
}

int main()
{
    string input;
    int index = 0;
    while (getline(cin, input)) {
        parseSudoku(input, index++);
    }

    vector<int> left; 
    do {
        for (int i = 0; i < unknownIndices.size(); i++) {
            int value = unknownIndices[i];
            int index = value & 0x0F;
            int subIndex = (value >> 4) & 0x0F;
             
            if (!figureOut(index, subIndex)) {
               left.push_back(value);
            }
        }
        unknownIndices.clear();
        unknownIndices.assign(left.begin(), left.end());
    } while (left.size() > 0);

    printSudoku();
    return 0;
}