判断数独板卡是否有效

Question

我遵循了Adnan等人的编程访谈C++元素中的一个解决方案。他们有这个解决方案来确定数独棋盘是否有效。

#include <iostream>
#include <vector>
#include <utility>
#include <cmath>
#include <deque>

using namespace std;

bool HasDuplicate(vector<vector<char>>& partial_assignment, int start_row, int end_row, int start_col, int end_col);

bool sudokuSolve(vector<vector<char>>& Board)
{
    // your code goes here
    // Check the row constraint

    // Check row constraint
    for (int i = 0; i < Board.size(); ++i)
    {
        if (HasDuplicate(Board, i, i + 1, 0, Board.size()))
            return false;
    }

    // Check column constraint
    for (int j = 0; j < Board.size(); ++j)
    {
        if (HasDuplicate(Board, 0, Board.size(), j, j + 1))
            return false;
    }

    // Check regional constraints
    int region_size = (int)sqrt(Board.size());
    for (int i = 0; i < region_size; ++i)
    {
        for (int j = 0; j < region_size; ++j)
        {
            if (HasDuplicate(Board, region_size * i, region_size * (i + 1), region_size * j, region_size * (j + 1)))
                return false;
        }
    }
    return true;
}

bool HasDuplicate(const vector<vector<int>>& partial_assignment, int start_row,
    int end_row, int start_col, int end_col)
{
    // this creates a container for bookkeeping of used numbers
    // size+1 because the number 1-x are used.
    deque<bool> is_present(size(partial_assignment) + 1, false);

    // The variables i and j are used to go through every coordinate on the
    // sudoku game board.
    for (int i = start_row; i < end_row; ++i)
    {
        for (int j = start_col; j < end_col; ++j)
        {
            // here it checks if the current number is already marked as used in "is_present"
            // if it is, then it's a duplicate and the function returns true.

            // The value 0 is used at coordinates where no number has been
            // selected.
            if (partial_assignment[i][j] != 0 && is_present[partial_assignment[i][j]])
                return true;

            // otherwise, mark the number as used
            is_present[partial_assignment[i][j]] = true;
        }

    }
    return false;
}

int main() {

    std::vector<std::vector<char>> board = {
    {'5','3','.','.','7','.','.','.','.'},
    {'6','.','.','1','9','5','.','.','.'},
    {'.','9','8','.','.','.','.','6','.'},
    {'8','.','.','.','6','.','.','.','3'},
    {'4','.','.','8','.','3','.','.','1'},
    {'7','.','.','.','2','.','.','.','6'},
    {'.','6','.','.','.','.','2','8','.'},
    {'.','.','.','4','1','9','.','.','5'},
    {'.','.','.','.','8','.','.','7','9'}
    };

    std::cout << sudokuSolve(board) << "\n";
    return 0;
}

不幸的是，作者提供的代码中似乎有一些错误。当我得到这些我无法修复的错误时：

1>------ Build started: Project: Test, Configuration: Debug Win32 ------
1>Source.obj : error LNK2019: unresolved external symbol "bool __cdecl HasDuplicate(class std::vector<class std::vector<char,class std::allocator<char> >,class std::allocator<class std::vector<char,class std::allocator<char> > > > &,int,int,int,int)" (?HasDuplicate@@YA_NAAV?$vector@V?$vector@DV?$allocator@D@std@@@std@@V?$allocator@V?$vector@DV?$allocator@D@std@@@std@@@2@@std@@HHHH@Z) referenced in function "bool __cdecl sudokuSolve(class std::vector<class std::vector<char,class std::allocator<char> >,class std::allocator<class std::vector<char,class std::allocator<char> > > > &)" (?sudokuSolve@@YA_NAAV?$vector@V?$vector@DV?$allocator@D@std@@@std@@V?$allocator@V?$vector@DV?$allocator@D@std@@@std@@@2@@std@@@Z)
1>  Hint on symbols that are defined and could potentially match:
1>    "bool __cdecl HasDuplicate(class std::vector<class std::vector<int,class std::allocator<int> >,class std::allocator<class std::vector<int,class std::allocator<int> > > > const &,int,int,int,int)" (?HasDuplicate@@YA_NABV?$vector@V?$vector@HV?$allocator@H@std@@@std@@V?$allocator@V?$vector@HV?$allocator@H@std@@@std@@@2@@std@@HHHH@Z)
1>C:\Dev\Test\Debug\Test.exe : fatal error LNK1120: 1 unresolved externals
1>Done building project "Test.vcxproj" -- FAILED.
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

有人能发现这个错误吗？

Answer 1

在开头有一个声明：

bool HasDuplicate(vector<vector<char>>& partial_assignment, int start_row, int end_row, int start_col, int end_col);

实际函数(使用不同的签名)如下：

bool HasDuplicate(const vector<vector<int>>& partial_assignment, int start_row, int end_row, int start_col, int end_col)

您可以决定vector的类型是int还是char，并进行相应的修复。

Answer 2

修正后的代码是。

#include <iostream>
#include <vector>
#include <utility>
#include <cmath>
#include <deque>

using namespace std;

bool HasDuplicate(vector<vector<char>>& partial_assignment, int start_row,
    int end_row, int start_col, int end_col)
{
    // this creates a container for bookkeeping of used numbers
    // size+1 because the number 1-x are used.
    deque<bool> is_present(partial_assignment.size() + 1, false);

    // The variables i and j are used to go through every coordinate on the
    // sudoku game board.
    for (int i = start_row; i < end_row; ++i)
    {
        for (int j = start_col; j < end_col; ++j)
        {
            // here it checks if the current number is already marked as used in "is_present"
            // if it is, then it's a duplicate and the function returns true.

            // The value 0 is used at coordinates where no number has been
            // selected.
            if (partial_assignment[i][j] != 0 && is_present[partial_assignment[i][j]])
                return true;

            // otherwise, mark the number as used
            is_present[partial_assignment[i][j]] = true;
        }

    }
    return false;
}

bool sudokuSolve(vector<vector<char>>& Board)
{
    // your code goes here
    // Check the row constraint

    // Check row constraint
    for (int i = 0; i < Board.size(); ++i)
    {
        if (HasDuplicate(Board, i, i + 1, 0, Board.size()))
            return false;
    }

    // Check column constraint
    for (int j = 0; j < Board.size(); ++j)
    {
        if (HasDuplicate(Board, 0, Board.size(), j, j + 1))
            return false;
    }

    // Check regional constraints
    int region_size = (int)sqrt(Board.size());
    for (int i = 0; i < region_size; ++i)
    {
        for (int j = 0; j < region_size; ++j)
        {
            if (HasDuplicate(Board, region_size * i, region_size * (i + 1), region_size * j, region_size * (j + 1)))
                return false;
        }
    }
    return true;
}



int main() {

    std::vector<std::vector<char>> board = {
    {'5','3','.','.','7','.','.','.','.'},
    {'6','.','.','1','9','5','.','.','.'},
    {'.','9','8','.','.','.','.','6','.'},
    {'8','.','.','.','6','.','.','.','3'},
    {'4','.','.','8','.','3','.','.','1'},
    {'7','.','.','.','2','.','.','.','6'},
    {'.','6','.','.','.','.','2','8','.'},
    {'.','.','.','4','1','9','.','.','5'},
    {'.','.','.','.','8','.','.','7','9'}
    };

    std::cout << sudokuSolve(board) << "\n";
    return 0;
}

更正: 1。更改了HasDuplicate签名，如果您在一个文件中编写，则不再预先声明它。