C++ 数独递归求解程序有效但最终什么都不输出

Question

我写了一个数独解法程序并编译了，但是好像不行。当我使用 printSuduku 函数在控制台上每一步打印数独时似乎完全没问题，但程序最终什么都不输出，我猜问题可能出在递归部分 Sudoku::solveSudoku。你能看一下代码吗？感谢您的帮助！

// sudoku.cpp

#include <iostream>
#include "Sudoku.h"

//int Sudoku::sudoku[] = {
//        3, 4, 0, 7, 0, 6, 0, 0, 1,
//        8, 7, 0, 0, 0, 0, 9, 0, 6,
//        0, 0, 0, 8, 9, 1, 0, 0, 3,
//        0, 0, 0, 0, 0, 3, 5, 6, 8,
//        6, 8, 0, 0, 5, 4, 0, 0, 7,
//        9, 1, 0, 6, 0, 0, 0, 0, 0,
//        0, 3, 0, 4, 0, 0, 0, 8, 0,
//        5, 9, 0, 0, 0, 0, 7, 3, 0,
//        7, 0, 0, 5, 3, 8, 0, 1, 9,
//};
int Sudoku::sudoku[] = { // sudoku on wiki
        5, 3, 0, 0, 7, 0, 0, 0, 0,
        6, 0, 0, 1, 9, 5, 0, 0, 0,
        0, 9, 8, 0, 0, 0, 0, 6, 0,
        8, 0, 0, 0, 6, 0, 0, 0, 3,
        4, 0, 0, 8, 0, 3, 0, 0, 1,
        7, 0, 0, 0, 2, 0, 0, 0, 6,
        0, 6, 0, 0, 0, 0, 2, 8, 0,
        0, 0, 0, 4, 1, 9, 0, 0, 5,
        0, 0, 0, 0, 8, 0, 0, 7, 9,
};
//int Sudoku::sudoku[] = {
//        0, 9, 0, 6, 0, 0, 0, 0, 5,
//        0, 6, 3, 0, 0, 5, 0, 7, 4,
//        0, 4, 1, 7, 0, 0, 0, 0, 0,
//        0, 0, 0, 3, 0, 0, 0, 9, 8,
//        0, 8, 4, 9, 6, 0, 0, 5, 1,
//        1, 0, 0, 0, 0, 7, 3, 0, 2,
//        7, 0, 0, 2, 0, 0, 0, 4, 0,
//        0, 0, 0, 0, 7, 9, 0, 3, 6,
//        0, 1, 0, 0, 4, 3, 0, 0, 0,
//};


bool Sudoku::solveSudoku(int subscript) {
    for(int attempt = 1; attempt <= 9; attempt++) {
        if(isSuitableAnswer(attempt, subscript)) {
            sudoku[subscript] = attempt;
//            printSudoku(subscript); // for test
            if(subscript >= 80 || solveSudoku(findNextBlank(subscript))) {
                return true;
            }
        }
    }
    sudoku[subscript] = 0;
    return false;
}

bool Sudoku::isSuitableAnswer(int attempt, int subscript) {
    return !hasSameInColumn(attempt, subscript) && !hasSameInRow(attempt, subscript) && !hasSameInBigBlock(attempt, subscript);
}

int Sudoku::findNextBlank(int subscript) {
    while(sudoku[subscript] != 0 || subscript >= 81) {
        subscript++;
    }
    return subscript;
}

bool Sudoku::hasSameInRow(int attempt, int subscript) {
    int beginSubscript = subscript / 9 * 9;
    int endSubscript = beginSubscript + 9;
    for(int i = beginSubscript; i < endSubscript; i++) {
        if(sudoku[i] == attempt) {
            return true;
        }
    }
    return false;
}

bool Sudoku::hasSameInColumn(int attempt, int subscript) {
    int beginSubscript = subscript % 9;
    int endSubscript = beginSubscript + 72;
    for(int i = beginSubscript; i <= endSubscript; i += 9) {
        if(sudoku[i] == attempt) {
            return true;
        }
    }
    return false;
}

bool Sudoku::hasSameInBigBlock(int attempt, int subscript) {
    int rowBeginSubscript = subscript % 9 / 3 * 3; // x
    int rowEndSubscript = rowBeginSubscript + 3; // y
    int columnBeginSubscript = subscript / 9 / 3 * 3;
    int columnEndSubscript = columnBeginSubscript + 3;

    for(int i = rowBeginSubscript; i < rowEndSubscript; i++) {
        for(int j = columnBeginSubscript; i < columnEndSubscript; i++) {
            if(sudoku[i + 9 * j] == attempt) {
                return true;
            }
        }
    }
    return false;
}

void Sudoku::printSudoku(int subscript) {
    int i = 0;
    std::string str;
    while(i < 81) {
        str += std::to_string(sudoku[i]);
        if(subscript != -1 && i == subscript) {
            str += "!";
        } else {
            str += " ";
        }
        if(i % 9 == 8) {
            str += '\n';
        }
        i++;
    }
    str += '\n';
    std::cout << str;
}

Sudoku::Sudoku() = default;

//sudoku.h

#ifndef SIMPLE_SUDOKU_SOLVER_SUDOKU_H
#define SIMPLE_SUDOKU_SOLVER_SUDOKU_H


class Sudoku {
private:
    static int sudoku[81];
public:
    /**
     * constructor
     */
    Sudoku();
    /**
     * todo
     * read in sudoku to array sudoku
     */
    void getSudokuContent();


    /**
     *
     * @param attempt
     * @param subscript
     * @return if there is another same number in current row
     */
    static bool hasSameInRow(int attempt, int subscript);

    /**
     *
     * @param attempt
     * @param subscript
     * @return if there is another same number in current column
     */
    static bool hasSameInColumn(int attempt, int subscript);

    /**
     *
     * @param attempt
     * @param subscript
     * @return if there is another same number in current big block made up by nine blocks
     */
    static bool hasSameInBigBlock(int attempt, int subscript);

    /**
     * solve sudoku
     * @param subscript array subscript of sudoku
     * @return is the array solved or not
     */
    bool solveSudoku(int subscript = findNextBlank(0));

    /**
     *
     * @param attempt
     * @param subscript
     * @return if this attempt suitable for current position
     */
    static bool isSuitableAnswer(int attempt, int subscript);

    /**
     *
     * @param subscript
     * @return the subscript of next blank in array sudoku
     */
    static int findNextBlank(int subscript);

    /**
     * prints out sudoku in console
     * only for testing or printing result
     * @param subscript the subscript that needs to be marked
     */
    static void printSudoku(int subscript = -1);

};


#endif //SIMPLE_SUDOKU_SOLVER_SUDOKU_H

// main
#include "Sudoku.h"

int main() {
    Sudoku a;
    if(a.solveSudoku()) {
        a.printSudoku();
    }
}

Answer 1

尝试 smaller/easier 示例。在你的情况下，你可以从维基百科中获取已知的解决方案，只遗漏一个数字。（这让我明白了你的第一个错误）

int Sudoku::sudoku[] = {
    5,3,4,6,7,8,9,1,2,
    6,7,2,1,9,5,3,4,8,
    1,9,8,3,4,2,5,6,7,
    8,5,9,7,6,1,4,2,3,
    4,2,6,8,5,3,7,9,1,
    7,1,3,9,2,4,8,5,6,
    9,6,1,5,3,7,2,8,4,
    2,8,7,4,1,9,6,3,5,
    3,4,5,2,8,6,0,7,9
};

然后通过翻出越来越多的数字来返回。一些额外的仪器可能会帮助你。例如打印出为什么尝试不合适，可能像这样：

bool Sudoku::isSuitableAnswer(int attempt, int subscript) {
    bool col = hasSameInColumn(attempt, subscript);
    bool row = hasSameInRow(attempt, subscript);
    bool big = hasSameInBigBlock(attempt, subscript);
    if (col)
        std::cout << std::to_string(attempt) << " fails the col\n";
    if (row)
        std::cout << std::to_string(attempt) << " fails the row\n";
    if (big)
        std::cout << std::to_string(attempt) << " fails the big\n";
    return !col && !row && !big;
}

C++ 数独递归求解程序有效但最终什么都不输出

C++ sudoku recursion solving program works but eventually outputs nothing

c++

arrays

recursion

sudoku