TransWikia.com

LeetCode 37: Sudoku Solver

Code Review Asked on November 13, 2021

I’m posting my code for a LeetCode problem. If you’d like to review, please do so. Thank you for your time!

Problem

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

  • Each of the digits 1-9 must occur exactly once in each row.
  • Each of the digits 1-9 must occur exactly once in each column.
  • Each of the the digits 1-9 must occur exactly once in each of the 9 3×3 sub-boxes of the grid.
  • Empty cells are indicated by the character ‘.’.

enter image description here

enter image description here

Inputs

[
    ["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"]
]

Outputs

[   ["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","1","7","9"]
]

Code

#include <bitset>
#include <array>
#include <vector>
#include <cassert>
#include <algorithm>
#include <utility>

struct Solution {
    inline void solveSudoku(std::vector<std::vector<char>> &board) {
        cells = std::array<std::array<cell, 9>, 9>();

        for (uint8_t row = 0; row < 9; row++) {
            for (uint8_t col = 0; col < 9; col++) {
                if (board[row][col] != '.' && !set(row, col, board[row][col] - '0')) {
                    return;
                }
            }
        }

        if (!find_values_for_empty_cells()) {
            return;
        }

        for (uint8_t row = 0; row < 9; row++) {
            for (uint8_t col = 0; col < 9; col++) {
                if (cells[row][col].value) {
                    board[row][col] = cells[row][col].value + '0';
                }
            }
        }
    }

private:
    const struct cell {
        uint8_t value;
        uint8_t possibilities;
        std::bitset<10> constraints;
        cell() : value(0), possibilities(9), constraints() {};
    };

    std::array<std::array<cell, 9>, 9> cells;

    const inline bool set(const uint8_t row, const uint8_t col, const uint8_t value) {
        cell &cell = cells[row][col];

        if (cell.value == value) {
            return true;
        }

        if (cell.constraints[value]) {
            return false;
        }

        cell.constraints = bitset<10>(0x3FE);
        cell.constraints.reset(value);
        cell.possibilities = 1;
        cell.value = value;

        for (uint8_t index = 0; index < 9; index++) {
            if (row != index && !update_constraints(index, col, value)) {
                return false;
            }

            if (col != index && !update_constraints(row, index, value)) {
                return false;
            }

            uint8_t curr_row = (row / 3) * 3 + index / 3;
            uint8_t curr_col = (col / 3) * 3 + index % 3;

            if (curr_row != row && curr_col != col && !update_constraints(curr_row, curr_col, value)) {
                return false;
            }
        }

        return true;
    }

    const inline bool update_constraints(const uint8_t row, const uint8_t col, const uint8_t excluded_value) {
        cell &cell = cells[row][col];

        if (cell.constraints[excluded_value]) {
            return true;
        }

        if (cell.value == excluded_value) {
            return false;
        }

        cell.constraints.set(excluded_value);

        if (--cell.possibilities > 1) {
            return true;
        }

        for (uint8_t value = 1; value < 10; value++) {
            if (!cell.constraints[value]) {
                return set(row, col, value);
            }
        }

        assert(false);
    }

    std::vector<std::pair<int, int>> backtrack_pairs;

    const inline bool find_values_for_empty_cells() {
        backtrack_pairs.clear();

        for (uint8_t row = 0; row < 9; row++) {
            for (uint8_t col = 0; col < 9; col++) {
                if (!cells[row][col].value) {
                    backtrack_pairs.push_back(make_pair(row, col));
                }
            }
        }

        std::sort(backtrack_pairs.begin(), backtrack_pairs.end(), [&](const pair<int, int> &a, const pair<int, int> &b) {
            return cells[a.first][a.second].possibilities < cells[b.first][b.second].possibilities;
        });

        return backtrack_find_value(0);
    }

    const inline bool backtrack_find_value(const uint8_t index) {
        if (index >= backtrack_pairs.size()) {
            return true;
        }

        uint8_t row = backtrack_pairs[index].first;
        uint8_t col = backtrack_pairs[index].second;

        if (cells[row][col].value) {
            return backtrack_find_value(index + 1);
        }

        auto constraints = cells[row][col].constraints;

        std::array<std::array<cell, 9>, 9> cells_snapshot(cells);

        for (uint8_t value = 1; value < 10; value++) {
            if (!constraints[value]) {
                if (set(row, col, value)) {
                    if (backtrack_find_value(index + 1)) {
                        return true;
                    }
                }

                cells = cells_snapshot;
            }
        }

        return false;
    }

};

References

algorithmbeginnerc++c++17programming challenge

One Answer

Error handling

Although the problem states that the input is a board with a unique solution, so this implies the input is always valid, it is good that you do validate the input. However, in case of an error you just call return, which doesn't really signal an error to the caller. Instead, I would throw a std::invalid_argument exception.

It's less clear what to do when the input is looking like a valid board, but you can't find a solution. But one could argue that this was then also because of an invalid argument to solveSudoku().

Start numbering from zero

In C and C++, we use zero-based numbering. You should do the same whereever possible. Don't be thrown off by the fact that Sudoku cells are filled with the characters '1' to '9', internally you can just assign those the integers 0 to 8. This will then get rid of some peculiarities with constraints, where the least significant bit is unused. In particular, to set all bits but one, you can now write:

cell.constraints.set(); // sets all bits
cell.constraints.reset(value);

Of course, now you have to change how you distinguish a filled-in cell from an empty cell, which brings me to:

Make empty cells explicit

Cells have a value, but the value 0 is treated specially to indicate an empty cell. While that's one way to do it, it does put a restriction on what values you can use. Also, there are now users of struct cell that also assume 0 is special. You should remove the implicit assumptions, and make the state of a cell (empty or filled-in) more explicit. One way would be to add a constant:

struct cell {
    static constexpr uint8_t EMPTY = 0;
    uint8_t value{EMPTY};
    ...
};

And then you can check if a cell is empty by writing:

if (cell.value == cell::EMPTY) {
    ...
}

And then if you ever need to change how values are stored, and need to change the value of an empty cell, you only need to change the constant. But, perhaps you want to change whether it is filled-in or not from a special value of value to another member variable. In that case, the above won't work anymore. An even better approach that does handle this scenario is to add a member function that can check if a cell is empty or not:

struct cell {
    uint8_t value{0};
    ...
    bool is_empty() const {
        return value == 0;
    }
};

And now it is easy to get rid of the special value that indicates an empty cell:

bool is_empty() const {
    return possibilities > 1;
}

Use default member initializers

Prefer using default member initializers to initialize struct members to constants. This avoids having to write a constructor in your case, and for more complex structs and classes with multiple constructors, it avoids having to repeat the member initializer list for each constructor. So:

struct cell {
    uint8_t value{};
    uint8_t possibilities{9};
    std::bitset<9> constraints{0x1FF};
    ...
};

You also wrote const struct cell, but the const doesn't do anything here.

Naming

Naming things is always hard. Try to give it some thought whenever you have to come up with a new name, and make sure that it is as meaningful and precise as possible. Some suggestions:

  • possibilities: it's not quite clear if this is a collection of possible values or a count. Since it is a count, I would write n_possibilities, where n_ is a common prefix meaning "number of".
  • backtrack_pair: ok, it has to do with backtracking, but the name it is a single pair of something... but what? Since this is a list of positions to check, how about positions_to_check? Note, that a backtracking algorithm is used to visit these positions doesn't not need to be mentioned in the name of this list.
  • cells, cells_snapshot: those are collections of cells indeed, but it's more common to call this a grid.
  • set(): this function does not unconditionally set the value of a cell, it rather tries to, but if it's not possible it will return false. A better name would therefore be try_set().

Use structured bindings

Make use of C++17's structured bindings. These are especially handy when using std::pairs. For example:

uint8_t row = backtrack_pairs[index].first;
uint8_t col = backtrack_pairs[index].second;

Can be rewritten to:

auto [row, col] = backtrack_pairs[index];

Answered by G. Sliepen on November 13, 2021

Add your own answers!

Ask a Question

Get help from others!

Recent Answers

Recent Questions

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP