闲时再弄弄, JS 还有些冗余的变量及逻辑
保存为 htm 文件, 浏览器 F12 控制台看运行- <script>
- var cntEmptyCell = 9 * 9;
- var schPath = [];
- var P = [[], [], [], [], [], [], [], [], []];
- // i 行 j 列
- for (let i = 0; i < 9; i++)
- for (let j = 0; j < 9; j++) {
- P[i][j] = {fill: 0, maybe: 0x1FF, choose: 9, block: (Math.floor(i / 3) * 3 + Math.floor(j / 3))};
- }
- var problems = [
- '001000008800010532750024090005302060670500004010780900098053406426179803537460219',
- '503092000700000008006007310020600000065000730007043500000706102070000800400009000',
- '700306000000000050060000018000081000000000000900000200000200900050400000080000007',
- '030000001200806000000005000000000000000000650043070000600002080090000000000010003',
- '010000200300800000000504000800090000000070120500000000000000000020130000400000005',
- '510000700076089000004000805400100007000030000090706010000460201047000300005000084'
- ];
- var problem;
- problem = problems[3];
- const LOOPCNT_CTRL = 50000;
- var LOOPCNT_OUTPUT_BEGIN = LOOPCNT_CTRL - 50;
- var a_p = Array.from(problem);
- var minchoose = 10, i_minchoose = 0, j_minchoose = 0;
- // 题面初始化
- for (let i = 0; i < 9; i++)
- for (let j = 0; j < 9; j++)
- if (a_p[i * 9 + j] - 0 != 0) {
- P[i][j].maybe = P[i][j].fill = 1 << (a_p[i * 9 + j] - 1);
- P[i][j].choose = 1;
- cntEmptyCell -= 1;
- for (let u = 0; u < 9; u++)
- if ((u != i) && (P[u][j].fill == 0)) {
- if ((P[u][j].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低
- P[u][j].choose -= 1;
- if (P[u][j].choose < minchoose) {
- minchoose = P[u][j].choose;
- i_minchoose = u;
- j_minchoose = j;
- }
- P[u][j].maybe &= ~(P[i][j].fill);
- }
- }
- for (let v = 0; v < 9; v++) {
- if ((v != j) && (P[i][v].fill == 0)) {
- if ((P[i][v].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低
- P[i][v].choose -= 1;
- if (P[i][v].choose < minchoose) {
- minchoose = P[i][v].choose;
- i_minchoose = i;
- j_minchoose = v;
- }
- P[i][v].maybe &= ~(P[i][j].fill);
- }
- }
- }
- g = P[i][j].block;
- // 3X3 块的左上角坐标
- r = Math.floor(g / 3) * 3;
- c = g % 3 * 3;
- for (let u = 0; u < 3; u++)
- for (let v = 0; v < 3; v++) {
- if (!(r + u == i && c + v == j) && (P[r + u][c + v].fill == 0)) {
- if ((P[r + u][c + v].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低
- P[r + u][c + v].choose -= 1;
- if (P[r + u][c + v].choose < minchoose) {
- minchoose = P[r + u][c + v].choose;
- i_minchoose = r + u;
- j_minchoose = c + v;
- }
- P[r + u][c + v].maybe &= ~(P[i][j].fill);
- }
- }
- }
- // console.log('F=' + a_p[i * 9 + j] + ', i=' + i + ', j=' + j + ', g=' + P[i][j].block + '\n');
- }
- console.log('题面初始化后\n');
- console.log('cntEmptyCell=' + cntEmptyCell + '\n');
- print_fill_intuitive();
- // 初始化尝试填数
- let try_num;
- try_num = 1 << 8;
- while ((try_num != 0) && ((P[i_minchoose][j_minchoose].maybe & try_num) == 0)) {
- try_num >>= 1;
- }
- if (try_num == 0) {
- throw 'error problem\n';
- }
- let maybe;
- let fail_flag = false;
- let success = false;
- let loopcnt = 0;
- // 节点状态:
- // NEW_POS: 填数未失败,新位置填第一个试数
- // NEXT_TRY: 失败换填下一个试数
- // UNDO_POS: 所有试数失败撤消填数
- let state_code = 'NEW_POS';
- do {
- loopcnt++;
- if (fail_flag) {
- // 撤消所有 SET_MAYBE
- while (schPath[0].type == 'SET_MAYBE') {
- P[schPath[0].row][schPath[0].col].maybe = schPath[0].oldMaybe;
- P[schPath[0].row][schPath[0].col].choose += 1;
- schPath.shift();
- }
- // 撤消 FILL_POS
- // 若 try_num 不是最后一个可试数,
- // try_num 取下一个可试数, fail_flag 设为 false
- if (schPath[0].type == 'FILL_POS') {
- i = schPath[0].row;
- j = schPath[0].col;
- P[i][j].fill = schPath[0].oldFill;
- P[i][j].choose = schPath[0].oldChoose;
- P[i][j].maybe = schPath[0].oldMaybe;
- if (schPath[0].oldFill == 0)
- cntEmptyCell += 1;
- // 下一个可试的数
- try_num = schPath[0].fillValue >> 1;
- schPath.shift();
- // 试探是否还有下一个可试填数
- while ((try_num != 0) && ((P[i][j].maybe & try_num) == 0)) {
- try_num >>= 1;
- }
- if (try_num != 0) {
- fail_flag = false;
- state_code = 'NEXT_TRY';
- } else {
- fail_flag = true;
- state_code = 'UNDO_POS';
- }
- }
- } else {
- if (state_code == 'NEW_POS') {
- if (cntEmptyCell == 0) {
- // 成功, 输出结果并退出
- console.log('\n\n' + 'SUCCESS! @ ' + 'loopcnt = ' + loopcnt + '\n\n' + 'problem and answer:\n\n' + PA_STR());
- print_fill_intuitive();
- // print_state();
- success = true;
- break;
- }
- minchoose = 10; // 准备搜索下一轮的最少选择位置
- i = i_minchoose;
- j = j_minchoose;
- // 初始化 try_num
- try_num = 1 << 8;
- while ((try_num != 0) && ((P[i][j].maybe & try_num) == 0)) {
- try_num >>= 1;
- }
- } else if (state_code == 'NEXT_TRY') {
- }
- if (try_num == 0) {
- throw 'BUG: try_num == 0';
- } else {
- // TRYFILL
- schPath.unshift({type: 'FILL_POS', oldFill: P[i][j].fill, row: i, col: j, fillValue: try_num, fillValue_fact: get_fill_intuitive(try_num), oldChoose: P[i][j].choose, oldMaybe: P[i][j].maybe});
- if (P[i][j].fill == 0)
- cntEmptyCell -= 1;
- P[i][j].choose = 1;
- P[i][j].maybe = try_num;
- P[i][j].fill = try_num;
- for (let u = 0; !fail_flag && (u < 9); u++)
- if ((u != i) && (P[u][j].fill == 0)) {
- if ((P[u][j].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低
- // 搜索栈压栈
- schPath.unshift({type: 'SET_MAYBE', row: u, col: j, oldMaybe: P[u][j].maybe});
- P[u][j].choose -= 1;
- if (P[u][j].choose < minchoose) {
- minchoose = P[u][j].choose;
- i_minchoose = u;
- j_minchoose = j;
- }
- maybe = P[u][j].maybe &= ~(P[i][j].fill);
- if (maybe == 0) {
- fail_flag = true;
- break;
- }
- }
- }
- for (let v = 0; !fail_flag && (v < 9); v++) {
- if ((v != j) && (P[i][v].fill == 0)) {
- if ((P[i][v].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低
- // 搜索栈压栈
- schPath.unshift({type: 'SET_MAYBE', row: i, col: v, oldMaybe: P[i][v].maybe});
- P[i][v].choose -= 1;
- if (P[i][v].choose < minchoose) {
- minchoose = P[i][v].choose;
- i_minchoose = i;
- j_minchoose = v;
- }
- maybe = P[i][v].maybe &= ~(P[i][j].fill);
- if (maybe == 0) {
- fail_flag = true;
- break;
- }
- }
- }
- }
- if (!fail_flag) {
- g = P[i][j].block;
- // 3X3 块的左上角坐标
- r = Math.floor(g / 3) * 3;
- c = g % 3 * 3;
- for (let u = 0; !fail_flag && (u < 3); u++)
- for (let v = 0; !fail_flag && (v < 3); v++) {
- if (!(r + u == i && c + v == j) && (P[r + u][c + v].fill == 0)) {
- if ((P[r + u][c + v].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低
- // 搜索栈压栈
- schPath.unshift({type: 'SET_MAYBE', row: r + u, col: c + v, oldMaybe: P[r + u][c + v].maybe});
- P[r + u][c + v].choose -= 1;
- if (P[r + u][c + v].choose < minchoose) {
- minchoose = P[r + u][c + v].choose;
- i_minchoose = r + u;
- j_minchoose = c + v;
- }
- maybe = P[r + u][c + v].maybe &= ~(P[i][j].fill);
- if (maybe == 0) {
- fail_flag = true;
- break;
- }
- }
- }
- }
- }
- for (let u = 0; u < 9; u++)
- for (let v = 0; v < 9; v++) {
- if (!(u == i && v == j) && P[u][v].fill == 0) {
- if (P[u][v].choose < minchoose) {
- minchoose = P[u][v].choose;
- i_minchoose = u;
- j_minchoose = v;
- }
- }
- }
- if (COUNT_EmptyCell() != cntEmptyCell) {
- throw 'BUG: COUNT_EmptyCell = ' + COUNT_EmptyCell();
- }
- }
- if (fail_flag) {
- state_code = 'NEXT_TRY';
- } else {
- state_code = 'NEW_POS';
- }
- }
- } while ((true || (loopcnt < LOOPCNT_CTRL)) && (schPath.length > 0 || (!fail_flag && state_code == 'NEXT_TRY' && try_num != 0)));
- function print_choose_num() {
- console.log('\n\n\n' + 'print_choose_num:' + '\n\n');
- for (let i = 0; i < 9; i++) {
- let line = i + ': ';
- for (let j = 0; j < 9; j++) {
- line += ((P[i][j].fill != 0) ? '+' : P[i][j].choose) + ' ';
- }
- console.log(line);
- }
- }
- function print_maybe_bin() {
- console.log('\n\n\n' + 'print_maybe_bin:' + '\n\n');
- for (let i = 0; i < 9; i++) {
- let line = i + ': ';
- for (let j = 0; j < 9; j++) {
- line += ('000000000' + P[i][j].maybe.toString(2)).slice(-9).replace(/0/g, '_') + ' ';
- }
- console.log(line);
- }
- }
- function print_block_num() {
- for (let i = 0; i < 9; i++) {
- let line = i + ': ';
- for (let j = 0; j < 9; j++) {
- line += ', ' + P[i][j].block;
- }
- console.log(line);
- }
- }
- function print_fill_bin() {
- console.log('\n\n\n' + 'print_fill_bin:' + '\n\n');
- for (let i = 0; i < 9; i++) {
- let line = i + ': ';
- for (let j = 0; j < 9; j++) {
- line += ('000000000' + P[i][j].fill.toString(2)).slice(-9).replace(/0/g, '_') + ' ';
- }
- console.log(line);
- }
- }
- function print_fill_intuitive() {
- console.log('\n\n\n' + 'print_fill_intuitive:' + '\n\n');
- for (let i = 0; i < 9; i++) {
- let line = i + ': ';
- for (let j = 0; j < 9; j++) {
- line += get_fill_intuitive(P[i][j].fill) + ' ';
- }
- console.log(line);
- }
- }
- function COUNT_EmptyCell() {
- let sum = 0;
- for (let i = 0; i < 9; i++)
- for (let j = 0; j < 9; j++)
- if (P[i][j].fill == 0)
- sum++;
- return sum;
- }
- function get_fill_intuitive(y) {
- if (y == 0) {
- return '_'
- } else
- return (Math.round(Math.log(y) / Math.log(2)) + 1);
- }
- function print_state() {
- console.log('\n\n\n' + 'BEGIN print_state:' + '\n\n');
- print_fill_intuitive();
- print_fill_bin();
- print_choose_num();
- print_maybe_bin();
- console.log('\n\n\n' + 'END print_state.' + '\n\n');
- console.log('\n\n\n' + 'loopcnt = ' + loopcnt);
- }
- function print_choose_state() {
- console.log('\n\n\n' + 'BEGIN print_choose_state:' + '\n\n');
- print_choose_num();
- print_maybe_bin();
- console.log('\n\n\n' + 'END print_choose_state.' + '\n\n');
- console.log('\n\n\n' + 'loopcnt = ' + loopcnt);
- }
- function PA_STR() {
- let t = problem;
- for (let i = 0; i < 9; i++)
- for (let j = 0; j < 9; j++)
- t += get_fill_intuitive(P[i][j].fill);
- return t;
- }
- /*
- 搜索算法
- 数组存储
- P 二维数组 9 行 X 9 列,
- 元素为对象 引用方式: P[行号,列号]
- {
- fill: 填数 -- 0 为未填,否则为已填的数值,
- maybe: 可选数的完全可能 -- 以2进制位表达,右至左数第1位表示可选1,第2位表示可选2,...第9位表示可选9, 当此属性值为0x1FF表示1~9全部可选,
- 当有任意一个位置的 maybe 为 0 时, 说明最后试填的数失败, 必须撤回
- choose: 可选数的数目 -- 也就是 maybe 的所有二进制位上 '1' 的总数,
- block: 区块号 -- 值范围[0..8]
- };
- cntEmptyCell -- 未填数单元格计数
- 解成功判断: if (cntEmptyCell == 0) 成功, 输出结果并退出
- 最大关联位置 -- 以当前线索简单判断最少可能选择的位置
- 节点状态:
- NEW_POS: 填数未失败,新位置填第一个试数
- NEXT_TRY: 失败换填下一个试数
- UNDO_POS: 所有试数失败撤消填数
- 初始化题面并找出最大关联位置
- 节点状态 = NEW_POS
- 试填失败标志: fail_flag = false
- :loop
- if (fail_flag == true) {
- 撤消搜索栈顶的所有 SET_MAYBE 操作并 弹栈搜索栈
- 撤消 FILL_POS 操作 弹栈搜索栈
- 如果 当前 处理位置还有可试填的其他数值可能(同时设置好下一个试填数值),
- fail_flag = false;
- 节点状态 = 'NEXT_TRY';
- 否则
- fail_flag = true;
- 节点状态 = 'UNDO_POS';
- } else {
- if (节点状态 == 'NEW_POS') {
- 检测解出是否成功(成功则输出并退出程序)
- 操作位置设为最大关联位置
- 找出操作位置上第一个可选数值(0x100 --> 0x1 的次序)
- }
- 执行 FILL_POS 操作 并 压栈搜索栈, 将同行同列同区块的 maybe 值作相应处理 并 压栈搜索栈, 找出所有未填数单元格中的 最大关联位置
- 处理 maybe 值时 如果 发现无解 (任意一个位置的 maybe == 0), 则 设置失败标志 fail_flag = true
- }
- 当 搜索栈未空 或 (fail_flag 为假 且 节点状态 == 'NEXT_TRY' 且 存在可试填数)
- goto :loop
- 搜索栈结构:
- 结点: {type: FILL_POS 或 SET_MAYBE, row:行坐标, col:列坐标, oldMaybe: Maybe原值, fillValue}
- type 为 FILL_POS 时, 有 fillValue 值
- fillValue 可能的值: 从 2 ** 8 (256) 0X100 开始 依次 >> 1 位, 直到 1, 不包括 0
- */
- </script>
复制代码
|