Solving Sudoku puzzles based on customized information entropy

solve.cpp

//
// Created by cryolitia on 24-1-16.
//

#include <iostream>
#include <vector>
#include <utility>
#include <unordered_set>
#include <cassert>
#include <memory>
#include <algorithm>
#include <random>

unsigned long long tries = 0;
unsigned int count = 0;

std::ostream &operator<<(std::ostream &out,
                         const std::vector<std::shared_ptr<const std::pair<std::unordered_set<unsigned int>, unsigned int>>> &chessboard) {
    for (int k = 0; k < 33; k++) {
        out << "=";
    }
    out << std::endl;
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            out << chessboard[i * 9 + j]->second << ((j != 8 && j % 3 == 2) ? " | " : "   ");
        }
        out << std::endl;
        if (i != 8 && i % 3 == 2) {
            for (int k = 0; k < 33; k++) {
                out << "-";
            }
        }
        if (i != 8) {
            out << std::endl;
        }
    }
    for (int k = 0; k < 33; k++) {
        out << "=";
    }
    out << std::endl << std::endl;
    return out;
}

bool
fill(std::vector<std::shared_ptr<const std::pair<std::unordered_set<unsigned int>, unsigned int>>> &chessboard,
     unsigned int x,
     unsigned int y,
     unsigned int value) {
    assert(x >= 0 && x < 9);
    assert(y >= 0 && y < 9);
    assert(chessboard[x * 9 + y]->second == 0);
    if (!chessboard[x * 9 + y]->first.contains(value)) {
        return false;
    }
    for (int i = 0; i < 9; i++) {
        if (chessboard[i * 9 + y]->second == value) {
            return false;
        }
    }
    for (int i = 0; i < 9; i++) {
        if (chessboard[x * 9 + i]->second == value) {
            return false;
        }
    }
    for (unsigned int i = x / 3 * 3; i < x / 3 * 3 + 3; i++) {
        for (unsigned int j = y / 3 * 3; j < y / 3 * 3 + 3; j++) {
            if (chessboard[i * 9 + j]->second == value) {
                return false;
            }
        }
    }
    for (int i = 0; i < 9; i++) {
        if (chessboard[i * 9 + y]->first.contains(value)) {
            auto block = std::make_shared<std::pair<std::unordered_set<unsigned int>, unsigned int>>(
                    *chessboard[i * 9 + y]);
            block->first.erase(value);
            chessboard[i * 9 + y] = block;
        }
    }
    for (int i = 0; i < 9; i++) {
        if (chessboard[x * 9 + i]->first.contains(value)) {
            auto block = std::make_shared<std::pair<std::unordered_set<unsigned int>, unsigned int>>(
                    *chessboard[x * 9 + i]);
            block->first.erase(value);
            chessboard[x * 9 + i] = block;
        }
    }
    for (unsigned int i = x / 3 * 3; i < x / 3 * 3 + 3; i++) {
        for (unsigned int j = y / 3 * 3; j < y / 3 * 3 + 3; j++) {
            if (chessboard[i * 9 + j]->first.contains(value)) {
                auto block = std::make_shared<std::pair<std::unordered_set<unsigned int>, unsigned int>>(
                        *chessboard[i * 9 + j]);
                block->first.erase(value);
                chessboard[i * 9 + j] = block;
            }
        }
    }
    chessboard[x * 9 + y] = std::make_shared<std::pair<std::unordered_set<unsigned int>, unsigned int>>(
            std::unordered_set<unsigned int>(), value);
    return true;
}

void try_fill(
        std::vector<std::shared_ptr<const std::pair<std::unordered_set<unsigned int>, unsigned int>>> chessboard,
        unsigned int process) {
    tries++;
    //std::cerr << tries << std::endl;
    //std::cerr << chessboard;
    unsigned int i = process;
    auto end = chessboard.end();
    for (auto it = chessboard.begin();; it++) {
        auto distance1 = std::distance(chessboard.begin(), it);
        auto distance2 = std::distance(chessboard.begin(), end);
        if (it == end) {
            break;
        }
        if (it == chessboard.end()) {
            if (end == chessboard.begin()) {
                break;
            }
            it = chessboard.begin();
        }
        if ((*it)->second == 0 && (*it)->first.size() == 1) {
            auto distance = std::distance(chessboard.begin(), it);
            unsigned int x = distance / 9;
            unsigned int y = distance % 9;
            if (!fill(chessboard, x, y, *chessboard[distance]->first.begin())) {
                return;
            } else {
                i++;
                end = it;
            }
        }
    }
    //std::cerr << chessboard;
    if (i == 81) {
        count++;
        std::cout << chessboard;
        std::cout << tries << std::endl;
        return;
    }

    auto min = std::min_element(chessboard.begin(), chessboard.end(), [](const auto & a, const auto & b){
        if (a->second != 0){
            return false;
        }
        if (b->second != 0) {
            return true;
        }
        return a->first.size() < b->first.size();
    });
    auto point = std::distance(chessboard.begin(), min);

    unsigned int x = point / 9;
    unsigned int y = point % 9;

    for (auto it: chessboard[point]->first) {
        auto try_chessboard = chessboard;
        if (fill(try_chessboard, x, y, it)) {
            try_fill(try_chessboard, i + 1);
        }
    }
}

int main() {
    std::vector<std::shared_ptr<const std::pair<std::unordered_set<unsigned int>, unsigned int>>> chessboard =
            std::vector(
                    81,
                    std::make_shared<const std::pair<std::unordered_set<unsigned int>, unsigned int>>(
                            std::pair<std::unordered_set<unsigned int>, unsigned int>(
                                    {std::unordered_set<unsigned int>(
                                            {1,
                                             2,
                                             3,
                                             4,
                                             5,
                                             6,
                                             7,
                                             8,
                                             9}),
                                     0})));

    int process = 0;
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            unsigned k;
            std::cin >> k;
            if (k != 0) {
                assert(fill(chessboard, i, j, k));
                process++;
            }
        }
    }

    try_fill(chessboard, process);
    std::cout << count << std::endl;
}

Zhai G, Zhang J. Solving Sudoku puzzles based on customized information entropy[J]. International Journal of Hybrid Information Technology, 2013, 6(1): 77-91.