← Real problems

noip09p4

mediumsearchbacktrackingbitmaskStatement on DMOJ

CP Lang

36 lines0.3 spec
// noip09p4 Target Sudoku: finish the grid maximizing the sum of digit times cell worth (10 at the
// centre, 6 on the rim), or -1. Backtrack, always branching on the blank with the fewest digits.
domain Line = 0..9
domain Cell = (Line, Line)
domain Digit = 1..=9
let given = read<[Line, Line]0..=9>()
var board: [Cell]?Digit = [Cell] p => Digit.at(given[p])
var in_row: [Line]Subset<Digit> = Subset.empty
var in_col: [Line]Subset<Digit> = Subset.empty
domain Band = 0..3
var in_box: [Band, Band]Subset<Digit> = Subset.empty
fn box(p: Cell) -> (Band, Band) = (Band(Int(p.0) / 3), Band(Int(p.1) / 3))
fn worth(p: Cell) -> Int = 10 - max(abs(Int(p.0) - 4), abs(Int(p.1) - 4))
fn toggle(p: Cell, d: Digit):
    in_row[p.0] = in_row[p.0] ^ Subset.single(d)
    in_col[p.1] = in_col[p.1] ^ Subset.single(d)
    in_box[box(p)] = in_box[box(p)] ^ Subset.single(d)
fn free(p: Cell) -> Subset<Digit> = (in_row[p.0] | in_col[p.1] | in_box[box(p)]).complement()
var score = 0
for p in Cell:
    if let d = board[p]:
        toggle(p, d)
        score += worth(p) * Int(d)
var best: ?Int = None
fn fill(score: Int):
    let p = Cell.filter(p => board[p] == None).min(by: p => free(p).len) else:
        best max= score
        return
    for d in free(p).items:
        toggle(p, d)
        board[p] = d
        fill(score + worth(p) * Int(d))
        board[p] = None
        toggle(p, d)
fill(score)
print(best ?? -1)

Accepted C++

102 lines · 5.42 s on the judge
#pragma GCC optimize("Ofast,unroll-loops")

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

constexpr int n = 9, scores[5] = {10, 9, 8, 7, 6};

int arr[n][n], ans = -1;
bool visr[n][n], visc[n][n], visg[3][3][n];

void dfs(int x, int y) {
    if (x == n) {
        int cans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cans += (arr[i][j] + 1) * scores[max(abs(i - 4), abs(j - 4))];
            }
        }
        ans = max(ans, cans);
        return;
    } else if (y == -1) {
        dfs(x + 1, n - 1);
        return;
    } else if (arr[x][y] != -1) {
        dfs(x, y - 1);
        return;
    }
    auto& cvg = visg[x / 3][y / 3];
    for (int i = 0; i < 9; i++) {
        if (!visr[x][i] && !visc[y][i] && !cvg[i]) {
            visr[x][i] = visc[y][i] = cvg[i] = true;
            arr[x][y] = i;
            dfs(x, y - 1);
            visr[x][i] = visc[y][i] = cvg[i] = false;
            arr[x][y] = -1;
        }
    }
}

void solve() {
    for (auto& a : arr) {
        for (auto& b : a) {
            cin >> b;
            b--;
        }
    }
    bool bad = false;
    auto upd = [&](bool& b) -> void {
        bad |= b;
        b = true;
    };
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j] != -1) {
                upd(visr[i][arr[i][j]]);
                upd(visc[j][arr[i][j]]);
                upd(visg[i / 3][j / 3][arr[i][j]]);
            }
        }
    }
    if (bad) {
        cout << -1 << endl;
        return;
    }
    dfs(0, n - 1);
    cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    solve();
}