Sudoku Solver (轻松/中等)

Question

我已经写了我的第一个真正的C++项目，一个数独解决！虽然不雅致，但效果很好。它解决了简单和中等，但不困难！

#include <locale>
#include <iostream>
#include <fstream>
#include <string>
#include <ctype.h>
#include <cstring>


const char test[11] = {'e', '1', '2', '3', '4', '5', '6', '7', '8', '9', '*'};


class Grid { // A Class With The Goal Of Solving A Sudoku

    public:

    char board[9][9] = { {0} }; // Declare (and apparently initialize) the sudoku grid array

    void mapChars(std::string fileName) { // function to get a users input sudoku file and parse to the array

        std::ifstream myfile (fileName.c_str());

        if (myfile.is_open()) {
            std::string line;
            unsigned int x = 0;
            unsigned int y = 0;
            while (getline(myfile,line)) {
                for(unsigned int i = 0; i < 20; i++) {
                    if(strchr(test, line[i]) != NULL){
                        if (line[i] == 'e') {
                            y++; x=0;
                        } else {
                            board[y][x] = line[i];
                            x++;
                        }
                    }
                }
            } myfile.close();
        }
    }

    void dumpMap() {
        for(unsigned int j = 0;j < 9;j++){
            for(unsigned int i = 0;i < 9;i++){
                std::cout << board[j][i] << ' ';
            }
            std::cout << std::endl;
        }
    }

    bool testGrid(char sType, char ident, unsigned int num) { // sType takes type { c: col , r: row, s: square, a: all
        unsigned int count = 0;
        if ( sType == 'r' ) {
            for(int it = 0; it < 9; it++) {
                if(board[num][it] == ident) { count = 1; }
            }
            if(count == 1){
                return true;
            } else {
                return false;
            }
                return false;
        }
        if ( sType == 'c' ) {
            for(int it = 0; it < 9; it++) {
                if(board[it][num] == ident) { count = 1; }
            }
            if(count == 1){
                return true;
            } else {
                return false;
            }
        }
        if ( sType == 's' ) {
            unsigned int startY = 0;
            unsigned int startX = 0;
            unsigned int count = 0;

            startY = (num / 3) * 3;
            startX = (num % 3) * 3;

            unsigned int rw = startY;
            unsigned int cl = startX;

            while(rw < (startY + 3)) {
                while(cl < (startX + 3)) {
                    if(board[rw][cl] == ident){ count = 1; }
                cl++;
                }
                rw++;
                cl = startX;
            }
            if(count == 1){
                return true;
            } else {
                return false;
            }
        }
                return false;
    }

    unsigned int wildCardCount() {
        unsigned int wildCards = 0;
       for(unsigned int j = 0;j < 9;j++){
            for(unsigned int i = 0;i < 9;i++){
                    if(board[j][i] == '*') { wildCards++; }
            }
        }
        return wildCards;
    }

    // find coords of first blank cell in square 1

void doStuff(int iter) {

    unsigned int startY = 0;
    unsigned int startX = 0;

    startY = (iter / 3) * 3;
    startX = (iter % 3) * 3;

    unsigned int rw = startY;
    unsigned int cl = startX;

    while(rw < (startY + 3)) {
        while(cl < (startX + 3)) {
            if(board[rw][cl] == '*'){

                char poss[9] = {'1','2','3','4','5','6','7','8','9'};
                unsigned int totalcount = 0;
                unsigned int possibilities = 0;

                for(unsigned int alpha = 0; alpha < 9; alpha++){

                    if (testGrid('r', poss[alpha], rw) == true) { totalcount++; }
                    if (testGrid('c', poss[alpha], cl) == true) { totalcount++; }
                    if (testGrid('s', poss[alpha], iter) == true) { totalcount++; }

                    if(totalcount == 0) { possibilities++; }

                    totalcount = 0;
                }

                //std::cout << possibilities << " possibilities" << std::endl;

                if(possibilities == 1) {
                    unsigned int possibleRow = rw;
                    unsigned int possibleCol = cl;
                    unsigned int lastCheck = 0;

                    for(unsigned int alpha = 0; alpha < 9; alpha++){
                        if (testGrid('r', poss[alpha], possibleRow) == true) { lastCheck++; }
                        if (testGrid('c', poss[alpha], possibleCol) == true) { lastCheck++; }
                        if (testGrid('s', poss[alpha], iter) == true) { lastCheck++; }
                        if(lastCheck == 0) { board[rw][cl] = poss[alpha]; }
                        lastCheck = 0;
                    }
                }
                possibilities = 0;
            }
            cl++;
        }
        rw++;
        cl = startX;
    }
}

} sudoku;

int main() {

    unsigned int initialBlanks = 0;

    sudoku.mapChars("med1.map");
    sudoku.dumpMap();
    initialBlanks = sudoku.wildCardCount();
    std::cout << std::endl << initialBlanks << " blanks remain." << std::endl << std::endl;;

    while(sudoku.wildCardCount() != 0){

        for(unsigned int beta = 0; beta < 10; beta++) {
            sudoku.doStuff(beta);
            sudoku.dumpMap();
            std::cout << std::endl << sudoku.wildCardCount() << " blanks remain." << std::endl << std::endl;;
        }
    }

    std::cout << std::endl << "Completed. " << initialBlanks << " blanks filled.";
    return 0;

    }

它需要一个.MAP文件，如下所示：

S*-*-*-e S-8-*-4-7-*-3-*-*-e S-7-9-2-6-**-e

我对自己满意吗？是。我说完了吗？不是的。

我现在需要计算出我需要做些什么来开始解决那些硬网格，整理代码并进行一些验证。

Answer 1

首先，请原谅我采取了简单的路线，只是评论你的代码结构和变量命名。

在testGrid中，您可以看到以下内容：

if ( sType == 'r' ) {
  //...
}
if ( sType == 'c' ) {
  //...
}
if ( sType == 's' ) {

通常，考虑使用else if。这暂时不会产生任何影响，但它增加了可读性(因为很明显，x的可能性之一将被执行)，如果您修改代码并执行两个分支而不是一个分支，可能会防止以后发现一些很难找到的but。

在本例中，这三个不相交的if()分支构成了整个函数，因此我建议创建三个独立的函数。这样，您就不需要传递任何sType，函数名将告诉您和任何读者正在发生什么(比较testGrid('r', 3, 0)与testRow(3, 0) )。

这还将为参数num提供一个更有意义的名称，比如row、col和square或square_nr。这也会对你有所帮助:如果你想优化行的代码，你不会被困在这个庞大的函数中，你也不用担心你会意外地破坏其他地方的东西。

(公平地说，“旗子”的想法听起来不错。它比一些神奇的if(nr == 2) { /* process a row */ }代码要好。

unsigned int startY = 0;
// ...
startY = (num / 3) * 3;

我马上就会做unsigned int startY = (num / 3) * 3; --这让我觉得= 0的声明和实际的初始化相隔几行，而这个0没有发生任何事情。或者将= 0放在声明中；这可能是最好的方法。

变量命名我将向rw和cl添加一个额外的字母，以使它们成为row和col，然后读者不必从rw = startY中扣除它确实是一个行号。

我不知道void doStuff(int iter)做什么，也不知道for循环中的计数器变量alpha和beta提供关于它们的意义的任何信息，以及正在迭代的内容。

您不仅帮助了代码阅读器，而且还帮助了您自己:如果您遍历行并适当地调用变量row，那么识别bug就不会那么麻烦了。如果您在某一点上引用board[col]而不是board[row]，我会说，与board[alpha]和board[beta]相比，您更有可能注意到错误，在这两种情况下，您必须记住变量来自哪个循环。

if(count == 1){
   return true;
} else {
   return false;
}
   return false;

一个return false太多了；您可以选择要删除哪一个(但是如果保留第二个，请修复第二个的缩进)。

在重命名doStuff之后，从这个函数中创建两个函数可能是明智的:一个函数遍历所有这些循环(入口点函数)，另一个函数检查是否可以将数字赋给单元格。

现在，doStuff通过两个whiles，一个if，一个for，然后几个if检查。如果你只有两个whiles，你的if细胞是*检查，然后类似examineCell(row, col)之类的东西，我知道“啊！他正在检查每个细胞，然后检查它是否是空的。”

Answer 2

硬网格通常需要猜测，然后再进行正常的求解。如果它失败了，那么您需要返回跟踪，并尝试另一个猜测。

我喜欢的一种方法是创建网格的“视图”对象。也就是说，每个视图都是一个由9个单元格组成的数组。为行、列和方格创建这些视图的单独数组。然后，您可以应用在任何视图上操作的一致规则。

网上有很多相关的信息。我只是擦破了表面。