Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
#include <string.h>
#include <stdbool.h>
#include "sc1.h"
#define DELTA_X 1
#define DELTA_Y N
#define NUM_OF_LINE (N + N + 2)
#define LINE_SUM 111
#define HOLE_NUM 15
#define REP(i, a, b) for (int i = (a); i<(b); ++i)
#define rep(i, n) REP(i, 0, n)
#define board s
typedef struct {
// 配列へのポインタ
int* ref;
// 終点の"次"
int* end;
// 増分
int delta;
// 行に何個穴があるか
int holeCount;
// 行の合計
int sum;
} LineRef;
// 行の走査用
// 0-5 : 縦
// 6-11 : 横
// 12-13 : ナナメ
// 14 : どうでもいいやつ
LineRef lines[NUM_OF_LINE + 1];
void initLines() {
// 縦向き
rep(i, N) {
lines[i].ref = board[0] + i;
lines[i].delta = DELTA_Y;
lines[i].end = board[N - 1] + i + lines[i].delta;
}
// 横向き
rep(i, N) {
lines[N + i].ref = board[i];
lines[N + i].delta = DELTA_X;
lines[N + i].end = board[i] + DELTA_Y - 1 + lines[N + i].delta;
}
// ナナメ1
lines[12].ref = board[0];
lines[12].delta = DELTA_X + DELTA_Y;
lines[12].end = board[N - 1] + N - 1 + lines[12].delta;
// ナナメ2
lines[13].ref = board[0] + N - 1;
lines[13].delta = DELTA_Y - DELTA_X;
lines[13].end = board[N - 1] + lines[13].delta;
}
// 穴が開いてる場所のインデックス
int holeIdxs[HOLE_NUM];
int unusedList[HOLE_NUM];
void initUnused() {
unsigned long long used = 0;
int count = 0;
rep(i, N) {
rep(j, N) {
if (board[i][j])
used |= (1ull << board[i][j]);
else {
holeIdxs[count] = i * 6 + j;
++count;
}
}
}
count = 0;
REP(i, 1, 1 + N*N) {
if (((used >> i) & 1) == 0) {
unusedList[count] = i;
++count;
}
}
}
// それぞれの列が使う可能性のある数字のunusedListの添字が立ってるBit列
int lineNeeds[NUM_OF_LINE + 1];
// n個の未使用数字のうちsumを構成できる可能性がある物を求める(bit列)
int lineCandidate(int used, int sum, int n) {
if (n == 1) {
int i = 0;
// lower_bound的なもの
for (; i < HOLE_NUM && unusedList[i] < sum; ++i) {}
return (
unusedList[i] == sum && ((used >> i) & 1) == 0
? 1 << i
: 0
);
}
int res = 0;
rep(i, HOLE_NUM) {
if (unusedList[i] > sum)
break;
if ((used & (1 << i)) == 0) {
int c = lineCandidate(used | (1 << i), sum - unusedList[i], n - 1);
res |= (c != 0 ? c | (1 << i) : 0);
}
}
return res;
}
void initLineNeeds() {
rep(i, NUM_OF_LINE) {
int* ref = lines[i].ref;
// 列にある穴の数
int holeCount = 0;
// 列の和
int sum = 0;
// 列を走査
while (ref != lines[i].end) {
sum += *ref;
holeCount += (*ref == 0 ? 1 : 0);
ref += lines[i].delta;
}
lines[i].holeCount = holeCount;
lines[i].sum = sum;
if(holeCount != 0)
lineNeeds[i] = lineCandidate(0, LINE_SUM - sum, holeCount);
}
lineNeeds[14] = -1;
// 適当に大きめの数
lines[14].holeCount = 3141592;
}
bool solve(int used, int n) {
const int x = holeIdxs[n] % N;
const int y = holeIdxs[n] / N;
int belongIdxs[3];
// 縦列
belongIdxs[0] = x;
// 横列
belongIdxs[1] = N + y;
// ナナメ(属していなければ14)
belongIdxs[2] = (x == y ? 12 : (x + y == N - 1 ? 13 : 14));
// 候補(bit列)
int candidate = ~used;
// 確定できるもの
int fixed = -1;
// マスが存在する列を走査
rep(i, 3) {
// 候補の絞込
candidate &= lineNeeds[belongIdxs[i]];
if (lines[belongIdxs[i]].holeCount == 1) {
const int needs = LINE_SUM - lines[belongIdxs[i]].sum;
if (fixed != -1) {
if (needs == unusedList[fixed])
continue;
else
return false;
}
int j = 0;
// lower_bound的なもの
for (; j < HOLE_NUM && unusedList[j] < needs; ++j) {}
// 必要な数と一致していて未使用なら
if (unusedList[j] == needs && ((used >> j) & 1) == 0)
fixed = j;
else
return false;
}
}
// 確定できる時
if (fixed != -1) {
(*board)[holeIdxs[n]] = unusedList[fixed];
if (n == HOLE_NUM - 1)
return true;
// 所属する列に登録
rep(i, 3) {
lines[belongIdxs[i]].sum += unusedList[fixed];
--lines[belongIdxs[i]].holeCount;
}
if (solve(used | 1 << fixed, n + 1))
return true;
// 元に戻す
rep(i, 3) {
lines[belongIdxs[i]].sum -= unusedList[fixed];
++lines[belongIdxs[i]].holeCount;
}
return false;
}
if (candidate == 0)
return false;
rep(i, HOLE_NUM) {
if ((candidate >> i) & 1) {
(*board)[holeIdxs[n]] = unusedList[i];
// 所属する列に登録
rep(j, 3) {
lines[belongIdxs[j]].sum += unusedList[i];
--lines[belongIdxs[j]].holeCount;
}
if (solve(used | 1 << i, n + 1))
return true;
// 元に戻す
rep(j, 3) {
lines[belongIdxs[j]].sum -= unusedList[i];
++lines[belongIdxs[j]].holeCount;
}
}
}
return false;
}
int main() {
input(board);
initUnused();
initLines();
initLineNeeds();
solve(0, 0);
output(board);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment