c++ - 如何制作一个 bool 数组来保存二维数组中大于 0 的数字的位置？

Question

我正在创建一个解决数独难题的算法，但其中一个要求是我必须创建一个 bool 数组来锁定任何分配数字的初始位置（在这种情况下，任何非 0 的数字）以便当算法运行时，它不会改变“锁定”的数字

基本上，下面的数组就是“拼图”本身，我需要创建一个 2D bool 数组来保存最初提供的数字的位置，以便算法以后在运行时无法更改它们

这是拼图本身和数据结构的代码：

#define N 9
typedef struct Coordinates
{

    int row;
    int column;

};

int sudokuArray[N][N] = {
            {0,0,0,6,0,0,4,0,0},
            {7,0,0,0,0,3,6,0,0},
            {0,0,0,0,9,1,0,8,0},
            {0,0,0,0,0,0,0,0,0},
            {0,5,0,1,8,0,0,0,3},
            {0,0,0,3,0,6,0,4,5},
            {0,4,0,2,0,0,0,6,0},
            {9,0,3,0,0,0,0,0,0},
            {0,2,0,0,0,0,1,0,0}
    };

标签： c++arraysdata-structures

Answer 1

您可以做一些内存效率较低但速度更快的事情：

与其存储值数组，不如存储值结构数组和布尔值，以判断给定位置是否可变。

#include <cstdint>
#include <array>

// Prefer constexpr to macros
constexpr uint32_t size = 9;

struct sudoku_field
{
    uint8_t value;
    bool is_mutable;
};

std::array<std::array<sudoku_field, size>, size> sudoku_board
{
    { {0, 0}, {0, 0}, {0, 0}, {6, 1}, {0, 0}, {0, 0}, {4, 1}, {0, 0}, {0, 0} },
    { {7, 1}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {3, 1}, {6, 1}, {0, 0}, {0, 0} },
    ...
}

当您需要测试字段是否应该是可变的时，这种方法将提供恒定的查找时间。

---

您的方法需要一个位置向量，其中该向量中的每个条目都是不可变的。

#include <vector>
#include <algorithm>

struct coordinates
{
    int8_t row;
    int8_t column;
};

std::vector<coordinates> immutable_positions;

// And this would be a test funciton
bool is_immutable(int8_t row, int8_t column)
{
    auto res = std::find(std::begin(immutable_positions), 
        std::end(immutable_positions), 
        coordinates{row, column});
    return res == std::end(immutable_positions);
}