[新手上路]批处理新手入门导读[视频教程]批处理基础视频教程[视频教程]VBS基础视频教程[批处理精品]批处理版照片整理器
[批处理精品]纯批处理备份&还原驱动[批处理精品]CMD命令50条不能说的秘密[在线下载]第三方命令行工具[在线帮助]VBScript / JScript 在线参考
12
返回列表 发帖
523066680

Rank: 7Rank: 7Rank: 7

帖子
3151 
积分
6455 
技术
317  
捐助
70  
注册时间
2008-8-3 
1楼 跳转到 » 正序看帖
打印
tT
发表于 2017-9-12 20:39 | 只看该作者

[挑战]解数独程序与数独题目生成

本帖最后由 523066680 于 2017-9-24 16:14 编辑

以下是从某网站提取的5种难度的数独游戏（难度从1-5，循着网站是可以找到答案的）：
001000008800010532750024090005302060670500004010780900098053406426179803537460219
503092000700000008006007310020600000065000730007043500000706102070000800400009000
700306000000000050060000018000081000000000000900000200000200900050400000080000007
030000001200806000000005000000000000000000650043070000600002080090000000000010003
010000200300800000000504000800090000000070120500000000000000000020130000400000005

写程序对这五个数独题目求解，并计算解每道题的时间消耗。
编程语言：不限

------------------------------------------ 2017-09-18补充 ------------------------------------------
如果解决上面五道题耗时不超过1秒，可以尝试批量解题库中的题，并统计时间消耗。

题库下载：http://523066680.ys168.com/
Perl/数独/数独题库200801-201709_含答案.zip

题库按键值对存储，key 是时间戳，value 中前81个字符是题目，后81个字符是唯一答案。
nd0 - nd4 表示不同的难度。
收藏 分享
FuniCode 编程论坛

CrLf

Rank: 8Rank: 8

帖子
6388 
积分
18843 
技术
982  
捐助
100  
注册时间
2010-10-9 
26楼
发表于 2017-10-11 13:39 | 只看该作者
回复 22# 523066680


    那个算法666，看来把人脑的算法套用给电脑，的确不合适
链接：在线第三方命令行工具下载   bat、vbs、js 原生混编

TOP

happy886rr

帖子
961 
积分
2350 
技术
334  
捐助
0  
注册时间
2016-3-7 
25楼
发表于 2017-10-11 12:49 | 只看该作者
回复 24# 523066680
不错，代码整理的很整齐。方便今后他人研究分析。

TOP

523066680

Rank: 7Rank: 7Rank: 7

帖子
3151 
积分
6455 
技术
317  
捐助
70  
注册时间
2008-8-3 
24楼
发表于 2017-10-11 12:14 | 只看该作者
本帖最后由 523066680 于 2017-10-17 11:00 编辑

正在学着用 github，代码已提交
https://github.com/vicyang/Sudoku/tree/master/Solver/DancingLinks

ChinaUnix 的rubyish把他的方案也写成了C版本，我在上面套了 fill_one_possible_num 函数 后，解sudoku17.txt 也是6秒，
在 i7 cpu 主机上面，3秒


Rubyish/solve_multiGame.c
FuniCode 编程论坛

TOP

happy886rr

帖子
961 
积分
2350 
技术
334  
捐助
0  
注册时间
2016-3-7 
23楼
发表于 2017-10-10 14:06 | 只看该作者
回复 22# 523066680
太牛叉了，4万道6秒。

TOP

523066680

Rank: 7Rank: 7Rank: 7

帖子
3151 
积分
6455 
技术
317  
捐助
70  
注册时间
2008-8-3 
22楼
发表于 2017-10-10 11:55 | 只看该作者

RE: [挑战]解数独程序与数独题目生成 —— Dancing Links 算法

本帖最后由 523066680 于 2017-10-10 14:25 编辑

Rosettacode 上面有一段js的示例，代码较长不粘贴了
http://rosettacode.org/wiki/Sudoku#JavaScript
效率是很高，但是实现细节有问题，某些题型会崩溃
  1. sudoku_nd3.txt

  2. //'7.56...19........89....8.....81.2.7...13..4.237...5.9.8.3..1.25...5....41........',

  3. //'.....4...7.......2.....61.....2.......4...3..8..79.6....78....9.36........1......',

  4. //'...3.1...49......638.......1.5..7.......9...8.........6...4...........5...3...71.',

  5. 

  6. sudoku_nd4.txt

  7. //'......3......2.1..1.84.9.....7....2..3.6...7...6.7...8....5846.2........9..1.....',

  8. //'.....53..6.....5.8...1...2.45.8...1.3.....4.5..2.........2.18....7.3..6..2...4...',

  9. //'....9..3...5..2.4.7.94....13.1....98.4.9........8..6..2...13..7..36...151....9...',
复制代码
开始我以为是 js 限制递归层数太少，用Perl和C分别实现后发现主要还是和实现有关，递归回溯过程的数据处理写对了就不会有崩溃的情况。

顺便贴一些相关的：
Python 版DLX实现
http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html
  1. #!/usr/bin/env python3

  2. # http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html

  3. 

  4. # Author: Ali Assaf <ali.assaf.mail@gmail.com>

  5. # Copyright: (C) 2010 Ali Assaf

  6. # License: GNU General Public License <http://www.gnu.org/licenses/>

  7. 

  8. from itertools import product

  9. 

  10. def solve_sudoku(size, grid):

  11.     R, C = size

  12.     N = R * C

  13.     X = ([("rc", rc) for rc in product(range(N), range(N))] +

  14.          [("rn", rn) for rn in product(range(N), range(1, N + 1))] +

  15.          [("cn", cn) for cn in product(range(N), range(1, N + 1))] +

  16.          [("bn", bn) for bn in product(range(N), range(1, N + 1))])

  17.     Y = dict()

  18.     for r, c, n in product(range(N), range(N), range(1, N + 1)):

  19.         b = (r // R) * R + (c // C) # Box number

  20.         Y[(r, c, n)] = [

  21.             ("rc", (r, c)),

  22.             ("rn", (r, n)),

  23.             ("cn", (c, n)),

  24.             ("bn", (b, n))]

  25.     X, Y = exact_cover(X, Y)

  26.     for i, row in enumerate(grid):

  27.         for j, n in enumerate(row):

  28.             if n:

  29.                 select(X, Y, (i, j, n))

  30.     for solution in solve(X, Y, []):

  31.         for (r, c, n) in solution:

  32.             grid[r][c] = n

  33.         yield grid

  34. 

  35. def exact_cover(X, Y):

  36.     X = {j: set() for j in X}

  37.     for i, row in Y.items():

  38.         for j in row:

  39.             X[j].add(i)

  40.     return X, Y

  41. 

  42. def solve(X, Y, solution):

  43.     if not X:

  44.         yield list(solution)

  45.     else:

  46.         c = min(X, key=lambda c: len(X[c]))

  47.         for r in list(X[c]):

  48.             solution.append(r)

  49.             cols = select(X, Y, r)

  50.             for s in solve(X, Y, solution):

  51.                 yield s

  52.             deselect(X, Y, r, cols)

  53.             solution.pop()

  54. 

  55. def select(X, Y, r):

  56.     cols = []

  57.     for j in Y[r]:

  58.         for i in X[j]:

  59.             for k in Y[i]:

  60.                 if k != j:

  61.                     X[k].remove(i)

  62.         cols.append(X.pop(j))

  63.     return cols

  64. 

  65. def deselect(X, Y, r, cols):

  66.     for j in reversed(Y[r]):

  67.         X[j] = cols.pop()

  68.         for i in X[j]:

  69.             for k in Y[i]:

  70.                 if k != j:

  71.                     X[k].add(i)

  72. 

  73. grid = [

  74.     [0,0,0,4,0,2,0,0,0],

  75.     [0,0,0,0,0,5,0,0,3],

  76.     [1,0,0,0,7,0,0,9,6],

  77.     [6,0,0,0,3,0,0,0,0],

  78.     [0,0,0,0,0,0,2,0,0],

  79.     [0,0,4,0,0,0,7,0,0],

  80.     [0,0,0,0,9,0,0,0,0],

  81.     [0,0,0,0,0,0,0,0,1],

  82.     [0,0,5,7,0,4,0,0,0]]

  83. 

  84. for solution in solve_sudoku((3, 3), grid):

  85.     print(*solution, sep='\n')
复制代码
跳跃的舞者，舞蹈链（Dancing Links）算法——求解精确覆盖问题
算法实践——舞蹈链（Dancing Links）算法求解数独

17提示数的题库资源
四万多道17提示数的数独题
用C链表实现的DLX算法，加-O2编译优化，i7 CPU，printf不计入，解这四万多题只要3-6秒。
（参考算法实践——舞蹈链（Dancing Links）算法求解数独 最后一个评论，这个人用C重新实现，也是3秒。）
1

评分人数

FuniCode 编程论坛

TOP

search_Sudoku

Rank: 2

帖子
21 
积分
101 
技术
10  
捐助
0  
注册时间
2017-10-2 
21楼
发表于 2017-10-2 02:02 | 只看该作者
闲时再弄弄, JS 还有些冗余的变量及逻辑
保存为 htm 文件, 浏览器 F12 控制台看运行
  1. <script>

  2.     var cntEmptyCell = 9 * 9;

  3.     var schPath = [];

  4.     var P = [[], [], [], [], [], [], [], [], []];

  5.     // i 行 j 列

  6.     for (let i = 0; i < 9; i++)

  7.         for (let j = 0; j < 9; j++) {

  8.             P[i][j] = {fill: 0, maybe: 0x1FF, choose: 9, block: (Math.floor(i / 3) * 3 + Math.floor(j / 3))};

  9.         }

  10.     var problems = [

  11.         '001000008800010532750024090005302060670500004010780900098053406426179803537460219',

  12.         '503092000700000008006007310020600000065000730007043500000706102070000800400009000',

  13.         '700306000000000050060000018000081000000000000900000200000200900050400000080000007',

  14.         '030000001200806000000005000000000000000000650043070000600002080090000000000010003',

  15.         '010000200300800000000504000800090000000070120500000000000000000020130000400000005',

  16.         '510000700076089000004000805400100007000030000090706010000460201047000300005000084'

  17.     ];

  18.     var problem;

  19.     problem = problems[3];

  20.     const LOOPCNT_CTRL = 50000;

  21.     var LOOPCNT_OUTPUT_BEGIN = LOOPCNT_CTRL - 50;

  22.     var a_p = Array.from(problem);

  23.     var minchoose = 10, i_minchoose = 0, j_minchoose = 0;

  24.     // 题面初始化

  25.     for (let i = 0; i < 9; i++)

  26.         for (let j = 0; j < 9; j++)

  27.             if (a_p[i * 9 + j] - 0 != 0) {

  28.                 P[i][j].maybe = P[i][j].fill = 1 << (a_p[i * 9 + j] - 1);

  29.                 P[i][j].choose = 1;

  30.                 cntEmptyCell -= 1;

  31.                 for (let u = 0; u < 9; u++)

  32.                     if ((u != i) && (P[u][j].fill == 0)) {

  33.                         if ((P[u][j].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低

  34.                             P[u][j].choose -= 1;

  35.                             if (P[u][j].choose < minchoose) {

  36.                                 minchoose = P[u][j].choose;

  37.                                 i_minchoose = u;

  38.                                 j_minchoose = j;

  39.                             }

  40.                             P[u][j].maybe &= ~(P[i][j].fill);

  41.                         }

  42.                     }

  43.                 for (let v = 0; v < 9; v++) {

  44.                     if ((v != j) && (P[i][v].fill == 0)) {

  45.                         if ((P[i][v].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低

  46.                             P[i][v].choose -= 1;

  47.                             if (P[i][v].choose < minchoose) {

  48.                                 minchoose = P[i][v].choose;

  49.                                 i_minchoose = i;

  50.                                 j_minchoose = v;

  51.                             }

  52.                             P[i][v].maybe &= ~(P[i][j].fill);

  53.                         }

  54.                     }

  55.                 }

  56.                 g = P[i][j].block;

  57.                 // 3X3 块的左上角坐标

  58.                 r = Math.floor(g / 3) * 3;

  59.                 c = g % 3 * 3;

  60.                 for (let u = 0; u < 3; u++)

  61.                     for (let v = 0; v < 3; v++) {

  62.                         if (!(r + u == i && c + v == j) && (P[r + u][c + v].fill == 0)) {

  63.                             if ((P[r + u][c + v].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低

  64.                                 P[r + u][c + v].choose -= 1;

  65.                                 if (P[r + u][c + v].choose < minchoose) {

  66.                                     minchoose = P[r + u][c + v].choose;

  67.                                     i_minchoose = r + u;

  68.                                     j_minchoose = c + v;

  69.                                 }

  70.                                 P[r + u][c + v].maybe &= ~(P[i][j].fill);

  71.                             }

  72.                         }

  73.                     }

  74.                 // console.log('F=' + a_p[i * 9 + j] + ', i=' + i + ', j=' + j + ', g=' + P[i][j].block + '\n');

  75.             }

  76.     console.log('题面初始化后\n');

  77.     console.log('cntEmptyCell=' + cntEmptyCell + '\n');

  78.     print_fill_intuitive();

  79.     // 初始化尝试填数

  80.     let try_num;

  81.     try_num = 1 << 8;

  82.     while ((try_num != 0) && ((P[i_minchoose][j_minchoose].maybe & try_num) == 0)) {

  83.         try_num >>= 1;

  84.     }

  85.     if (try_num == 0) {

  86.         throw 'error problem\n';

  87.     }

  88.     let maybe;

  89.     let fail_flag = false;

  90.     let success = false;

  91.     let loopcnt = 0;

  92.     // 节点状态:

  93.     // NEW_POS: 填数未失败,新位置填第一个试数

  94.     // NEXT_TRY: 失败换填下一个试数

  95.     // UNDO_POS: 所有试数失败撤消填数

  96.     let state_code = 'NEW_POS';

  97.     do {

  98.         loopcnt++;

  99.         if (fail_flag) {

  100.             // 撤消所有 SET_MAYBE

  101.             while (schPath[0].type == 'SET_MAYBE') {

  102.                 P[schPath[0].row][schPath[0].col].maybe = schPath[0].oldMaybe;

  103.                 P[schPath[0].row][schPath[0].col].choose += 1;

  104.                 schPath.shift();

  105.             }

  106.             // 撤消 FILL_POS

  107.             // 若 try_num 不是最后一个可试数,

  108.             // try_num 取下一个可试数, fail_flag 设为 false

  109.             if (schPath[0].type == 'FILL_POS') {

  110.                 i = schPath[0].row;

  111.                 j = schPath[0].col;

  112.                 P[i][j].fill = schPath[0].oldFill;

  113.                 P[i][j].choose = schPath[0].oldChoose;

  114.                 P[i][j].maybe = schPath[0].oldMaybe;

  115.                 if (schPath[0].oldFill == 0)

  116.                     cntEmptyCell += 1;

  117.                 // 下一个可试的数

  118.                 try_num = schPath[0].fillValue >> 1;

  119.                 schPath.shift();

  120.                 // 试探是否还有下一个可试填数

  121.                 while ((try_num != 0) && ((P[i][j].maybe & try_num) == 0)) {

  122.                     try_num >>= 1;

  123.                 }

  124.                 if (try_num != 0) {

  125.                     fail_flag = false;

  126.                     state_code = 'NEXT_TRY';

  127.                 } else {

  128.                     fail_flag = true;

  129.                     state_code = 'UNDO_POS';

  130.                 }

  131.             }

  132.         } else {

  133.             if (state_code == 'NEW_POS') {

  134.                 if (cntEmptyCell == 0) {

  135.                     // 成功, 输出结果并退出

  136.                     console.log('\n\n' + 'SUCCESS! @ ' + 'loopcnt = ' + loopcnt + '\n\n' + 'problem and answer:\n\n' + PA_STR());

  137.                     print_fill_intuitive();

  138.                     // print_state();

  139.                     success = true;

  140.                     break;

  141.                 }

  142.                 minchoose = 10; // 准备搜索下一轮的最少选择位置

  143.                 i = i_minchoose;

  144.                 j = j_minchoose;

  145.                 // 初始化 try_num

  146.                 try_num = 1 << 8;

  147.                 while ((try_num != 0) && ((P[i][j].maybe & try_num) == 0)) {

  148.                     try_num >>= 1;

  149.                 }

  150.             } else if (state_code == 'NEXT_TRY') {

  151.             }

  152.             if (try_num == 0) {

  153.                 throw 'BUG: try_num == 0';

  154.             } else {

  155.                 // TRYFILL

  156.                 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});

  157.                 if (P[i][j].fill == 0)

  158.                     cntEmptyCell -= 1;

  159.                 P[i][j].choose = 1;

  160.                 P[i][j].maybe = try_num;

  161.                 P[i][j].fill = try_num;

  162.                 for (let u = 0; !fail_flag && (u < 9); u++)

  163.                     if ((u != i) && (P[u][j].fill == 0)) {

  164.                         if ((P[u][j].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低

  165.                             // 搜索栈压栈

  166.                             schPath.unshift({type: 'SET_MAYBE', row: u, col: j, oldMaybe: P[u][j].maybe});

  167.                             P[u][j].choose -= 1;

  168.                             if (P[u][j].choose < minchoose) {

  169.                                 minchoose = P[u][j].choose;

  170.                                 i_minchoose = u;

  171.                                 j_minchoose = j;

  172.                             }

  173.                             maybe = P[u][j].maybe &= ~(P[i][j].fill);

  174.                             if (maybe == 0) {

  175.                                 fail_flag = true;

  176.                                 break;

  177.                             }

  178.                         }

  179.                     }

  180.                 for (let v = 0; !fail_flag && (v < 9); v++) {

  181.                     if ((v != j) && (P[i][v].fill == 0)) {

  182.                         if ((P[i][v].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低

  183.                             // 搜索栈压栈

  184.                             schPath.unshift({type: 'SET_MAYBE', row: i, col: v, oldMaybe: P[i][v].maybe});

  185.                             P[i][v].choose -= 1;

  186.                             if (P[i][v].choose < minchoose) {

  187.                                 minchoose = P[i][v].choose;

  188.                                 i_minchoose = i;

  189.                                 j_minchoose = v;

  190.                             }

  191.                             maybe = P[i][v].maybe &= ~(P[i][j].fill);

  192.                             if (maybe == 0) {

  193.                                 fail_flag = true;

  194.                                 break;

  195.                             }

  196.                         }

  197.                     }

  198.                 }

  199.                 if (!fail_flag) {

  200.                     g = P[i][j].block;

  201.                     // 3X3 块的左上角坐标

  202.                     r = Math.floor(g / 3) * 3;

  203.                     c = g % 3 * 3;

  204.                     for (let u = 0; !fail_flag && (u < 3); u++)

  205.                         for (let v = 0; !fail_flag && (v < 3); v++) {

  206.                             if (!(r + u == i && c + v == j) && (P[r + u][c + v].fill == 0)) {

  207.                                 if ((P[r + u][c + v].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低

  208.                                     // 搜索栈压栈

  209.                                     schPath.unshift({type: 'SET_MAYBE', row: r + u, col: c + v, oldMaybe: P[r + u][c + v].maybe});

  210.                                     P[r + u][c + v].choose -= 1;

  211.                                     if (P[r + u][c + v].choose < minchoose) {

  212.                                         minchoose = P[r + u][c + v].choose;

  213.                                         i_minchoose = r + u;

  214.                                         j_minchoose = c + v;

  215.                                     }

  216.                                     maybe = P[r + u][c + v].maybe &= ~(P[i][j].fill);

  217.                                     if (maybe == 0) {

  218.                                         fail_flag = true;

  219.                                         break;

  220.                                     }

  221.                                 }

  222.                             }

  223.                         }

  224.                 }

  225.                 for (let u = 0; u < 9; u++)

  226.                     for (let v = 0; v < 9; v++) {

  227.                         if (!(u == i && v == j) && P[u][v].fill == 0) {

  228.                             if (P[u][v].choose < minchoose) {

  229.                                 minchoose = P[u][v].choose;

  230.                                 i_minchoose = u;

  231.                                 j_minchoose = v;

  232.                             }

  233.                         }

  234.                     }

  235.                 if (COUNT_EmptyCell() != cntEmptyCell) {

  236.                     throw 'BUG: COUNT_EmptyCell = ' + COUNT_EmptyCell();

  237.                 }

  238.             }

  239.             if (fail_flag) {

  240.                 state_code = 'NEXT_TRY';

  241.             } else {

  242.                 state_code = 'NEW_POS';

  243.             }

  244.         }

  245.     } while ((true || (loopcnt < LOOPCNT_CTRL)) && (schPath.length > 0 || (!fail_flag && state_code == 'NEXT_TRY' && try_num != 0)));

  246.     function print_choose_num() {

  247.         console.log('\n\n\n' + 'print_choose_num:' + '\n\n');

  248.         for (let i = 0; i < 9; i++) {

  249.             let line = i + ': ';

  250.             for (let j = 0; j < 9; j++) {

  251.                 line += ((P[i][j].fill != 0) ? '+' : P[i][j].choose) + ' ';

  252.             }

  253.             console.log(line);

  254.         }

  255.     }

  256.     function print_maybe_bin() {

  257.         console.log('\n\n\n' + 'print_maybe_bin:' + '\n\n');

  258.         for (let i = 0; i < 9; i++) {

  259.             let line = i + ': ';

  260.             for (let j = 0; j < 9; j++) {

  261.                 line += ('000000000' + P[i][j].maybe.toString(2)).slice(-9).replace(/0/g, '_') + ' ';

  262.             }

  263.             console.log(line);

  264.         }

  265.     }

  266.     function print_block_num() {

  267.         for (let i = 0; i < 9; i++) {

  268.             let line = i + ': ';

  269.             for (let j = 0; j < 9; j++) {

  270.                 line += ', ' + P[i][j].block;

  271.             }

  272.             console.log(line);

  273.         }

  274.     }

  275.     function print_fill_bin() {

  276.         console.log('\n\n\n' + 'print_fill_bin:' + '\n\n');

  277.         for (let i = 0; i < 9; i++) {

  278.             let line = i + ': ';

  279.             for (let j = 0; j < 9; j++) {

  280.                 line += ('000000000' + P[i][j].fill.toString(2)).slice(-9).replace(/0/g, '_') + ' ';

  281.             }

  282.             console.log(line);

  283.         }

  284.     }

  285.     function print_fill_intuitive() {

  286.         console.log('\n\n\n' + 'print_fill_intuitive:' + '\n\n');

  287.         for (let i = 0; i < 9; i++) {

  288.             let line = i + ': ';

  289.             for (let j = 0; j < 9; j++) {

  290.                 line += get_fill_intuitive(P[i][j].fill) + ' ';

  291.             }

  292.             console.log(line);

  293.         }

  294.     }

  295.     function COUNT_EmptyCell() {

  296.         let sum = 0;

  297.         for (let i = 0; i < 9; i++)

  298.             for (let j = 0; j < 9; j++)

  299.                 if (P[i][j].fill == 0)

  300.                     sum++;

  301.         return sum;

  302.     }

  303.     function get_fill_intuitive(y) {

  304.         if (y == 0) {

  305.             return '_'

  306.         } else

  307.             return (Math.round(Math.log(y) / Math.log(2)) + 1);

  308.     }

  309.     function print_state() {

  310.         console.log('\n\n\n' + 'BEGIN print_state:' + '\n\n');

  311.         print_fill_intuitive();

  312.         print_fill_bin();

  313.         print_choose_num();

  314.         print_maybe_bin();

  315.         console.log('\n\n\n' + 'END print_state.' + '\n\n');

  316.         console.log('\n\n\n' + 'loopcnt = ' + loopcnt);

  317.     }

  318.     function print_choose_state() {

  319.         console.log('\n\n\n' + 'BEGIN print_choose_state:' + '\n\n');

  320.         print_choose_num();

  321.         print_maybe_bin();

  322.         console.log('\n\n\n' + 'END print_choose_state.' + '\n\n');

  323.         console.log('\n\n\n' + 'loopcnt = ' + loopcnt);

  324.     }

  325.     function PA_STR() {

  326.         let t = problem;

  327.         for (let i = 0; i < 9; i++)

  328.             for (let j = 0; j < 9; j++)

  329.                 t += get_fill_intuitive(P[i][j].fill);

  330.         return t;

  331.     }

  332. /*

  333. 搜索算法

  334. 数组存储

  335. P 二维数组 9 行 X 9 列,

  336.     元素为对象 引用方式: P[行号,列号]

  337.         {

  338.             fill:   填数 -- 0 为未填,否则为已填的数值,

  339.             maybe:  可选数的完全可能 -- 以2进制位表达,右至左数第1位表示可选1,第2位表示可选2,...第9位表示可选9, 当此属性值为0x1FF表示1~9全部可选,

  340.                     当有任意一个位置的 maybe 为 0 时, 说明最后试填的数失败, 必须撤回

  341.             choose: 可选数的数目 -- 也就是 maybe 的所有二进制位上 '1' 的总数,

  342.             block:  区块号 -- 值范围[0..8]

  343.          };

  344. cntEmptyCell -- 未填数单元格计数

  345. 解成功判断: if (cntEmptyCell == 0) 成功, 输出结果并退出

  346. 最大关联位置 -- 以当前线索简单判断最少可能选择的位置

  347. 节点状态:

  348. NEW_POS: 填数未失败,新位置填第一个试数

  349. NEXT_TRY: 失败换填下一个试数

  350. UNDO_POS: 所有试数失败撤消填数

  351. 初始化题面并找出最大关联位置

  352. 节点状态 = NEW_POS

  353. 试填失败标志: fail_flag = false

  354. :loop

  355. if (fail_flag == true) {

  356.     撤消搜索栈顶的所有 SET_MAYBE 操作并 弹栈搜索栈

  357.     撤消 FILL_POS 操作 弹栈搜索栈

  358.     如果 当前 处理位置还有可试填的其他数值可能(同时设置好下一个试填数值),

  359.         fail_flag = false;

  360.         节点状态 = 'NEXT_TRY';

  361.     否则

  362.         fail_flag = true;

  363.         节点状态 = 'UNDO_POS';

  364. } else {

  365.     if (节点状态 == 'NEW_POS') {

  366.         检测解出是否成功(成功则输出并退出程序)

  367.         操作位置设为最大关联位置

  368.         找出操作位置上第一个可选数值(0x100 --> 0x1 的次序)

  369.     }

  370.     执行 FILL_POS 操作 并 压栈搜索栈, 将同行同列同区块的 maybe 值作相应处理 并 压栈搜索栈, 找出所有未填数单元格中的 最大关联位置

  371.     处理 maybe 值时 如果 发现无解 (任意一个位置的 maybe == 0), 则 设置失败标志 fail_flag = true

  372. }

  373. 当 搜索栈未空 或 (fail_flag 为假 且 节点状态 == 'NEXT_TRY' 且 存在可试填数)

  374.     goto :loop

  375. 搜索栈结构:

  376. 结点: {type: FILL_POS 或 SET_MAYBE, row:行坐标, col:列坐标, oldMaybe: Maybe原值, fillValue}

  377. type 为 FILL_POS 时, 有 fillValue 值

  378. fillValue 可能的值: 从 2 ** 8 (256) 0X100 开始 依次 >> 1 位, 直到 1, 不包括 0

  379. */

  380. </script>
复制代码
1

评分人数

TOP

523066680

Rank: 7Rank: 7Rank: 7

帖子
3151 
积分
6455 
技术
317  
捐助
70  
注册时间
2008-8-3 
20楼
发表于 2017-9-24 15:49 | 只看该作者
本帖最后由 523066680 于 2017-9-24 16:09 编辑

回复 19# bbaa

      对于题目和结果判断，你先用现成的题库弄上网站跑跑看？我前面发的题库分为5种难度等级，你可以随机抽取。
这些题只有一种答案，也都在文件里了，检验方便。（虽然这样提供了作弊条件，可以直接POST现有答案，不过也就是试试效果）
FuniCode 编程论坛

TOP

bbaa

Rank: 3Rank: 3

帖子
316 
积分
275 
技术
32  
捐助
0  
注册时间
2015-11-30 
19楼
发表于 2017-9-23 21:18 | 只看该作者
回复 18# bbaa


    随机法真的 身败名裂
  1. Allowed memory size of 134217728 bytes exhausted (tried to allocate 40 bytes)
复制代码
http://123456

TOP

bbaa

Rank: 3Rank: 3

帖子
316 
积分
275 
技术
32  
捐助
0  
注册时间
2015-11-30 
18楼
发表于 2017-9-23 19:56 | 只看该作者
我来了,等下用我之前的生成类试试
http://123456

TOP

slore

Rank: 5Rank: 5

帖子
281 
积分
1063 
技术
22  
捐助
0  
注册时间
2008-9-12 
17楼
发表于 2017-9-20 20:21 | 只看该作者
回复 16# 523066680

VBS当时写代码,就有这个逻辑.先CreatePlan里面有presolvecount,然后才SolvePanes递归的.

TOP

523066680

Rank: 7Rank: 7Rank: 7

帖子
3151 
积分
6455 
技术
317  
捐助
70  
注册时间
2008-8-3 
16楼
发表于 2017-9-20 16:36 | 只看该作者
本帖最后由 523066680 于 2017-9-20 20:34 编辑

回复 15# slore

对于回溯法，有一个优化很有效果。示意图（注意除了中间有个独立的候选数字2，右上角还有个框选的数字8）：


程序给定的单元候选数字中，大多单元格有多个可选数字，但是可以进一步排除。例如：
如果累计一行中的所有候选数，某个数字只出现一次，那么这个数字就是必选数字。同样，一列、一宫(3x3 block)的区域内也是如此。

我为程序增加了一个while 循环，反复筛选并填充唯一的数字，直到再也没有，然后才开始递归解题。

Sudoku:
3,0,0,0,1,0,0,0,0
0,0,0,0,0,0,0,9,0
0,8,0,2,0,0,0,0,6
0,0,0,0,7,0,3,4,0
0,5,6,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0
0,0,0,5,0,0,0,0,0
0,0,0,6,0,8,0,0,2
1,0,0,0,0,0,0,3,0

Fill only one possible cells
R:1 C:8 Fill:3
R:3 C:5 Fill:6
R:3 C:8 Fill:5
R:6 C:5 Fill:1
R:0 C:1 Fill:6
R:1 C:4 Fill:6
R:6 C:0 Fill:6
R:8 C:6 Fill:6
R:5 C:7 Fill:6
R:8 C:2 Fill:5
R:8 C:8 Fill:8
R:6 C:2 Fill:8
R:6 C:7 Fill:7

Result:
3,6,0,0,1,0,0,0,0
0,0,0,0,6,0,0,9,3
0,8,0,2,0,0,0,0,6
0,0,0,0,7,6,3,4,5
0,5,6,0,0,0,0,0,0
0,0,0,0,0,0,0,6,0
6,0,8,5,0,1,0,7,0
0,0,0,6,0,8,0,0,2
1,0,5,0,0,0,6,3,8

Solve:
3,6,9,4,1,5,2,8,7
2,4,1,8,6,7,5,9,3
5,8,7,2,9,3,4,1,6
8,1,2,9,7,6,3,4,5
9,5,6,3,8,4,7,2,1
4,7,3,1,5,2,8,6,9
6,3,8,5,2,1,9,7,4
7,9,4,6,3,8,1,5,2
1,2,5,7,4,9,6,3,8
time used: 0.211s
FuniCode 编程论坛

TOP

slore

Rank: 5Rank: 5

帖子
281 
积分
1063 
技术
22  
捐助
0  
注册时间
2008-9-12 
15楼
发表于 2017-9-20 16:09 | 只看该作者
至于探索路径，不一定非要0～81这个顺序，可以把每个格子的候选项，从小到大排列，按这个数据填，有大概率先填入正确的数据，可以减少尝试次数吧。


错了，如果按候选项探索的话，比如, [0,0]点可以用5和4,[8,8]可以用1,3，
都是最小的2个候选，但是填写0,0，在填8,8，变成了散点，如果50%概率选错了的话，
其他格子，无效探索反而变得多了，填写的多，但是排除无效值的情报却少了。

探索改成下面这样。

先选择出有最少候选项的位置，然后对它相同X,Y和Z区域的 格子 权值-1。
(假设最小的这个格子我们填入了一个数字，被影响的其他格子，候选项-1)
然后，被影响的格子里面，权值最低的(候选项-1后，最小的)，
是我们接下来优先探索的，同理，整理出，每次填入一个单元格，
受其影响的，候选项最少的格的探索路径。这样填入数据之间有关联，
如果填入了错误值，可以更早地回溯。

VBS代码移植为ruby脚本的，只在处理前，修改这1处，从几百秒到稳定10秒LEVEL4的结果输出，
很大的改善方案。

ans = candidate(x, y)
return false if ans.size <= 0

v = ans[0]  #取出候选的第一个
ans.delete v
@matrix[x][y] = v

改成， v = ans.sample #候选中随机抽1个，LEVEL4的结果，2秒～18秒之间 
  1. #魔法CODE

  2. str.reserse!

  3. v = ans.sample
复制代码
  1.     sort_seq = []

  2.     while

  3.       sort_seq.push @solve_seq[min_seq]

  4.       x = @solve_seq[min_seq][0]

  5.       y = @solve_seq[min_seq][1]

  6.       z = ((x / 3) * 3) + (y / 3)

  7.       @solve_seq.delete_at(min_seq)

  8. 

  9.       break if @solve_seq.size == 0

  10.       min = 10

  11.       min_seq = -1

  12.       @solve_seq.each_with_index do |seq, i|

  13.         zz = ((seq[0] / 3) * 3) + (seq[1] / 3)

  14.         if seq[0] == x || seq[1] == y || zz == z

  15.           seq[2] -= 1

  16.           if seq[2] < min

  17.             min = seq[2]

  18.             min_seq = i

  19.           end

  20.         end

  21.       end

  22.     end

  23.     p sort_seq

  24.     @solve_seq = sort_seq
复制代码

TOP

slore

Rank: 5Rank: 5

帖子
281 
积分
1063 
技术
22  
捐助
0  
注册时间
2008-9-12 
14楼
发表于 2017-9-20 13:02 | 只看该作者
本帖最后由 slore 于 2017-9-20 13:03 编辑 
  1. class Soduku

  2.   def initialize(str)

  3.     @matrix = 9.times.map{[0]*9}

  4.     str.reverse!       <-只加了一句，LEVEL4立马难度变低了

  5.     nums = str.split('').map(&:to_i)

  6.     ...

  7.   end
复制代码
[3, 0, 0, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 9, 0]
[0, 8, 0, 2, 0, 0, 0, 0, 6]
[0, 0, 0, 0, 7, 0, 3, 4, 0]
[0, 5, 6, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 5, 0, 0, 0, 0, 0]
[0, 0, 0, 6, 0, 8, 0, 0, 2]
[1, 0, 0, 0, 0, 0, 0, 3, 0]
5.069903 秒
[3, 6, 9, 4, 1, 5, 2, 8, 7]
[2, 4, 1, 8, 6, 7, 5, 9, 3]
[5, 8, 7, 2, 9, 3, 4, 1, 6]
[8, 1, 2, 9, 7, 6, 3, 4, 5]
[9, 5, 6, 3, 8, 4, 7, 2, 1]
[4, 7, 3, 1, 5, 2, 8, 6, 9]
[6, 3, 8, 5, 2, 1, 9, 7, 4]
[7, 9, 4, 6, 3, 8, 1, 5, 2]
[1, 2, 5, 7, 4, 9, 6, 3, 8]

TOP

slore

Rank: 5Rank: 5

帖子
281 
积分
1063 
技术
22  
捐助
0  
注册时间
2008-9-12 
13楼
发表于 2017-9-20 10:02 | 只看该作者
回复 12# 523066680


单纯考虑算法的话，肯定有更优的，但是 多线程对于现在大内存，多核CPU才是更好的利用，而且很多问题都可以采用这个方法来提高。
至于探索路径，不一定非要0～81这个顺序，可以把每个格子的候选项，从小到大排列，按这个数据填，有大概率先填入正确的数据，可以减少尝试次数吧。那天有时间了ruby写下试试。

TOP

12
返回列表