-
rubyish
- 渐入佳境
- 帖子: 52
- 注册时间: 2018年04月23日 09:58
-
联系:
帖子
由 rubyish »
來一個 2023年的版本。移除一些冗餘的。。
- c
/*[ 2023/03/19 00:25 ]*/
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
int BITS[1 << 10];
typedef struct ijk Ijk;
typedef struct sudoku Sudoku;
struct ijk {
int i, j, k;
};
struct sudoku {
int dat[9][9];
Ijk todo[81];
int len;
int i[9], j[9], k[9];
};
void fill(int*);
void init(Sudoku*, char*);
void print(Sudoku*);
int gimme(Sudoku*, int);
void bless(Sudoku*, int);
bool play(Sudoku*, int);
// main
int main(void) {
fill(BITS);
// clang-format off
char* data[] = {
"001000008800010532750024090005302060670500004010780900098053406426179803537460219",
"503092000700000008006007310020600000065000730007043500000706102070000800400009000",
"700306000000000050060000018000081000000000000900000200000200900050400000080000007",
"030000001200806000000005000000000000000000650043070000600002080090000000000010003",
"010000200300800000000504000800090000000070120500000000000000000020130000400000005"
};
// clang-format on
Sudoku it;
for (int i = 0; i < 5; i++) {
init(&it, data[i]);
printf("[%d] --------------\n", i);
//print(&it);
//pp(" -----------------\n");
play(&it, 0);
}
}
void fill(int* b) {
for (int i = 1; i < (1 << 10); i++)
b[i] = b[i >> 1] + (i & 1);
}
void print(Sudoku* it) {
float exp;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (it->dat[i][j] < 0) {
exp = -it->dat[i][j];
// IEEE 754
it->dat[i][j] = ((*(int*)&exp) >> 23) - 127;
}
}
#define E(x) it->dat[i][x]
printf(
" %d %d %d %d %d %d %d %d %d\n",
E(0), E(1), E(2), E(3), E(4),
E(5), E(6), E(7), E(8)
);
#undef E
}
}
void init(Sudoku* it, char* dat) {
for (int i = 0; i < 9; i++) {
// 0b1111111110
it->i[i] = 1022;
it->j[i] = 1022;
it->k[i] = 1022;
}
it->len = 0;
for (int x = 0; x < 81; x++) {
int i = x / 9;
int j = x % 9;
int k = 3 * (i / 3) + j / 3;
int n = dat[x] - '0';
it->dat[i][j] = n;
if (n == 0) {
it->todo[it->len++] = (Ijk){i, j, k};
} else {
it->i[i] ^= 1 << n;
it->j[j] ^= 1 << n;
it->k[k] ^= 1 << n;
}
}
}
void bless(Sudoku* it, int i) {
int min = gimme(it, i);
if (min < 2) return;
int k = i;
for (int j = i + 1; j < it->len; j++) {
int x = gimme(it, j);
if (x < min) {
min = x;
k = j;
if (min < 2) break;
}
}
if (k != i) {
Ijk tmp = it->todo[i];
it->todo[i] = it->todo[k];
it->todo[k] = tmp;
}
}
inline int gimme(Sudoku* it, int i) {
#define X (it->todo[i])
return BITS[it->i[X.i] & it->j[X.j] & it->k[X.k]];
#undef X
}
bool play(Sudoku* it, int x) {
if (x == it->len) {
print(it);
return true;
}
bless(it, x);
// bless(it, x);
int i = it->todo[x].i;
int j = it->todo[x].j;
int k = it->todo[x].k;
int test = it->i[i] & it->j[j] & it->k[k];
while (test) {
int pick = test & -test;
test -= pick;
it->dat[i][j] = -pick;
it->i[i] ^= pick;
it->j[j] ^= pick;
it->k[k] ^= pick;
bool ok = play(it, x + 1);
if (ok) return true;
it->i[i] |= pick;
it->j[j] |= pick;
it->k[k] |= pick;
}
return false;
}
上次由
rubyish 在 2023年04月05日 12:09,总共编辑 1 次。
$_
-
rubyish
- 渐入佳境
- 帖子: 52
- 注册时间: 2018年04月23日 09:58
-
联系:
帖子
由 rubyish »
my $exp = unpack 'i', pack 'f', 8;
$exp = ($exp >> 23) - 127;
$_
正浏览此版面之用户: Ahrefs [Bot] 和 1 访客