kubok-solver/kubok_solver.cpp at main · benjamin-githubprofile/kubok-solver · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include "kubok_solver.h"
#include "utils.h"
#include <iostream>
#include <iomanip>

KubokSolver::KubokSolver(const Puzzle &puz) : puzzle(puz) {}

bool KubokSolver::is_valid(const vector<vector<int> > &grid, const vector<int> &row_sums, const vector<int> &col_sums) {
    for (int i = 0; i < 4; ++i) {
        int rowSum = grid[i][0] + grid[i][1] + grid[i][2] + grid[i][3];
        int colSum = grid[0][i] + grid[1][i] + grid[2][i] + grid[3][i];
        if (rowSum != row_sums[i] || colSum != col_sums[i]) {
            return false;
        }
    }
    return true;
}

bool KubokSolver::isInvalidPlace(vector<vector<int> > &grid, const vector<int> &row_sums, const vector<int> &col_sums, int row, int col, int num) {
    int rowSum = grid[row][0] + grid[row][1] + grid[row][2] + grid[row][3];
    if (rowSum > row_sums[row]) {
        return true;
    }

    int colSum = grid[0][col] + grid[1][col] + grid[2][col] + grid[3][col];
    if (colSum > col_sums[col]) {
        return true;
    }

    int zeroCnt = 0;
    for (int k = 0; k < 4; k++) {
        if (grid[row][k] == 0) {
            zeroCnt += 1;
        }
    }
    if (zeroCnt == 0 && rowSum < row_sums[row]) {
        return true;
    }

    zeroCnt = 0;
    for (int k = 0; k < 4; k++) {
        if (grid[k][col] == 0) {
            zeroCnt += 1;
        }
    }
    if (zeroCnt == 0 && colSum < col_sums[col]) {
        return true;
    }

    return false;
}

bool KubokSolver::validRowColSum(vector<vector<int> > &grid, const vector<int> &row_sums, const vector<int> &col_sums, int row, int col) {
    int rowSum = grid[row][0] + grid[row][1] + grid[row][2] + grid[row][3];
    if (rowSum != row_sums[row]) {
        return false;
    }

    return true;
}

// Recursive function to solve the puzzle
bool KubokSolver::solve(vector<vector<int> > &grid, const vector<int> &row_sums, const vector<int> &col_sums, int row, int col, vector<bool> &used_numbers) {
    if (row == 4) {
        return is_valid(grid, row_sums, col_sums);
    }

    if (col == 4) {
        if (validRowColSum(grid, row_sums, col_sums, row, col - 1)) {
            return solve(grid, row_sums, col_sums, row + 1, 0, used_numbers);
        }
        else {
            return false;
        }
    }

    if (grid[row][col] != 0) {
        return solve(grid, row_sums, col_sums, row, col + 1, used_numbers);
    }

    for (int num = 1; num <= 16; ++num) {
        if (used_numbers[num]) continue;
        if (isInvalidPlace(grid, row_sums, col_sums, row, col, num)) {
            continue;
        }

        used_numbers[num] = true;
        grid[row][col] = num;
        if (solve(grid, row_sums, col_sums, row, col + 1, used_numbers)) {
            return true;
        }

        used_numbers[num] = false;
        grid[row][col] = 0;
    }

    return false;
}

bool KubokSolver::solve() {
    vector<bool> used_numbers(17, false);

    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (puzzle.grid[i][j] != 0) {
                used_numbers[puzzle.grid[i][j]] = true;
            }
        }
    }
    return solve(puzzle.grid, puzzle.rowSums, puzzle.columnSums, 0, 0, used_numbers);
}


void KubokSolver::displayResult() {
    cout << "  ";
    for (int i = 0; i < 4; i++) {
        cout << setw(3) << right << puzzle.columnSums[i];
    }
    cout << endl;
    for (int i = 0; i < 4; i++) {
        cout << setw(2) << puzzle.rowSums[i];
        for (int j = 0; j < 4; j++) {
            cout << setw(3) << right << puzzle.grid[i][j];
        }
        cout << endl;
    }
}