SudokuSolver 2.4 程序实现
本次版本实现了 用C++实现的数独解题程序 SudokuSolver 2.3 及实例分析 里发现的第三个不完全收缩 grp 算法 thirdGreenWorld。
CQuizDealer 类声明部分的修改
class CQuizDealer{public: ... void run(ulong tilsteps = 0); void mode(std::string& ex) { size_t pos = ex.find_first_not_of(" \t"); if (pos != std::string::npos) { ex.erase(0, pos); m_mode = (u8)strtoul(ex.c_str(), 0, 10); } printf("Working mode:%d (1:grp-only; 2:ply-only; other:both grp and ply)\n", (int)m_mode); } ... private: ... CQuizDealer() : m_state(STA_UNLOADED), ..., m_mode(0) {}; ... bool completeShrinkByGrp(u8* pGrp); u8 incompleteShrinkByGrp(u8* pGrp); u8 firstGreenWorld(u8* pGrp); u8 incompleteShrinkBy1GW(u8 valSum, u8* pCelSumExs, u8* pGrp); bool sameCandidates(u8 cel1, u8 cel2); u8 anotherGreenWorld(u8* pGrp); u8 incompleteShrinkByAGW(u8 times, u8* pTimesVals, u8* pValsCells, u8* pGrp); u8 thirdGreenWorld(u8* pGrp); u8 incompleteShrinkBy3GW(u8 sum, std::set<u8>& valSet, u8* pGrp); bool unionValsByCombi(u8 sum, u8* pCombi, u8* pGrp, std::set<u8>& unionSet); ... ulong m_steps; u8 m_mode; // 1:grp-only; 2:ply-only; other:both ...};
去掉了 setOnlyGrpMode 接口,新增了 mode 接口,相应地,原先的 onlygrp 命令换成了 mode [1|2|0] 命令。
增加了 thirdGreenWorld 等接口。
filterCandidates 接口的小修改
u8 CQuizDealer::filterCandidates(){ incSteps(); u8 ret = RET_PENDING; if (m_mode != 2) { for (u8 row = 0; row < 9; ++row) if (ret = filterRowGroup(row)) return ret; for (u8 col = 0; col < 9; ++col) if (ret = filterColGroup(col)) return ret; for (u8 blk = 0; blk < 9; ++blk) if (ret = filterBlkGroup(blk)) return ret; } if (m_mode != 1) { for (u8 row = 0; row < 9; ++row) { ret = filterRowCandidatesEx(row); if (IsDone(ret)) return ret; } for (u8 col = 0; col < 9; ++col) { ret = filterColCandidatesEx(col); if (IsDone(ret)) return ret; } } if (ret == RET_SHRUNKEN) { printf("incomplete shrink met, filter again\n"); return filterCandidates(); } return ret;}
修改后,可以只使用 grp 算法求解,也可以只使用 ply 算法求解,缺省是两者都用。
从旧的 filterOneGroup 接口实现中提炼出 firstGreenWorld
1 u8 CQuizDealer::firstGreenWorld(u8* pGrp) 2 { 3 u8 size = pGrp[0]; 4 u8 celSumExs[100] = {0}; 5 for (u8 idx = 1; idx <= size; ++idx) { 6 u8 valSum = m_seqCell[pGrp[idx]].candidates[0]; 7 u8 base = valSum * 10; 8 celSumExs[base] += 1; 9 u8 pos = base + celSumExs[base];10 celSumExs[pos] = pGrp[idx];11 }12 for (u8 idx = 2; idx <= 6; ++idx) {13 u8 ret = incompleteShrinkBy1GW(idx, celSumExs, pGrp);14 if (ret != RET_PENDING)15 return ret;16 }17 return RET_PENDING;18 }
旧 incompleteShrinkByGrp 改为 incompleteShrinkBy1GW
1 u8 CQuizDealer::incompleteShrinkBy1GW(u8 valSum, u8* pCelSumExs, u8* pGrp) 2 { 3 u8 base = valSum * 10; 4 if (pCelSumExs[base] < valSum) 5 return RET_PENDING; 6 u8 itemSum = 0; 7 Item items[9]; 8 for (u8 pos = 1; pos <= pCelSumExs[base]; ++pos) { 9 u8 idx = 0;10 for (; idx < itemSum; ++idx)11 if (sameCandidates(pCelSumExs[base + pos], items[idx].celIdxs[0])) {12 items[idx].celIdxs[items[idx].sameSum] = pCelSumExs[base + pos];13 items[idx].sameSum++;14 break;15 }16 if (idx == itemSum) {17 items[itemSum].sameSum = 1;18 items[itemSum].celIdxs[0] = pCelSumExs[base + pos];19 ++itemSum;20 }21 }22 for (u8 idx = 0; idx < itemSum; ++idx) {23 if (items[idx].sameSum > valSum)24 return RET_WRONG;25 }26 bool shrunken = false;27 for (u8 idx = 0; idx < itemSum; ++idx) {28 if (items[idx].sameSum < valSum)29 continue;30 for (u8 pos = 1; pos <= pGrp[0]; ++pos) {31 if (inSet(pGrp[pos], (u8*)&(items[idx])))32 continue;33 u8 isVals[10] = {0};34 u8 cel1 = items[idx].celIdxs[0];35 u8 cel2 = pGrp[pos];36 intersection(m_seqCell[cel1].candidates, m_seqCell[cel2].candidates, isVals);37 if (isVals[0] == 0)38 continue;39 shrunken = true;40 for (u8 valIdx = 1; valIdx <= isVals[0]; ++valIdx) {41 if (!removeVal(m_seqCell[cel2].candidates, isVals[valIdx]))42 return RET_WRONG;43 else44 printf("1GW: %d shrunken out of [%d,%d]\n", (int)isVals[valIdx], (int)cel2 / 9 + 1, (int)cel2 % 9 + 1);45 }46 }47 }48 return (shrunken ? RET_SHRUNKEN : RET_PENDING);49 }
新的 incompleteShrinkByGrp 接口实现
1 u8 CQuizDealer::incompleteShrinkByGrp(u8* pGrp) 2 { 3 u8 ret = firstGreenWorld(pGrp); 4 if (ret != RET_PENDING) 5 return ret; 6 ret = anotherGreenWorld(pGrp); 7 if (ret != RET_PENDING) 8 return ret; 9 return thirdGreenWorld(pGrp);10 }
新的 filterOneGroup 接口实现
u8 CQuizDealer::filterOneGroup(u8* pGrp){ return (completeShrinkByGrp(pGrp) ? RET_OK : incompleteShrinkByGrp(pGrp));}
incompleteShrinkByAGW 接口实现的 bug 修改
u8 CQuizDealer::incompleteShrinkByAGW(u8 times, u8* pTimesVals, u8* pValsCells, u8* pGrp){ ... while (true) { u8 celSet[10] = {0}; u8 valSet[10] = {0}; if (matchValsCells(times, combi, pTimesVals, pValsCells, celSet, valSet)) { valSet[0] = times; bool shrunken = false; for (u8 idx = 1; idx <= times; ++idx) { ... if (candiSum < times) { printf("2GW: [%d,%d] candidates %d lower than times %d!\n", (int)(cel / 9 + 1), (int)(cel % 9 + 1), (int)candiSum, (int)times); return RET_WRONG; } shrunken = true; for (u8 pos = 1; pos <= m_seqCell[cel].candidates[0];) { u8 val = m_seqCell[cel].candidates[pos]; if (inSet(val, valSet)) ++pos; else { removeVal(m_seqCell[cel].candidates, val); printf("2GW: %d shrunken out of [%d,%d]\n", (int)val, (int)(cel / 9 + 1), (int)(cel % 9 + 1)); } } } ... } if (!move2NextCombi(times, combi)) break; } return RET_PENDING;}
新增 thirdGreenWorld 接口实现
1 u8 CQuizDealer::thirdGreenWorld(u8* pGrp) 2 { 3 u8 grpSize = pGrp[0]; 4 std::set<u8> valSet; 5 u8 lowSum = 9, highSum = 0; 6 for (u8 idx = 1; idx <= grpSize; ++idx) { 7 u8 valSum = m_seqCell[pGrp[idx]].candidates[0]; 8 if (valSum < lowSum) 9 lowSum = valSum;10 if (valSum > highSum)11 highSum = valSum;12 for (u8 vidx = 1; vidx <= valSum; ++vidx) {13 u8 val = m_seqCell[pGrp[idx]].candidates[vidx];14 valSet.insert(val);15 }16 }17 if (valSet.size() != grpSize) {18 printf("3GW: shrink went wrong\n");19 return RET_WRONG;20 }21 if (highSum == valSet.size())22 --highSum;23 for (u8 sum = lowSum; sum <= highSum; ++sum) {24 u8 ret = incompleteShrinkBy3GW(sum, valSet, pGrp);25 if (ret != RET_PENDING)26 return ret;27 }28 return RET_PENDING;29 }
新增 incompleteShrinkBy3GW 接口实现
1 u8 CQuizDealer::incompleteShrinkBy3GW(u8 sum, std::set<u8>& valSet, u8* pGrp) 2 { 3 u8 combi[10] = {0}; 4 combi[0] = pGrp[0]; 5 for (u8 idx = 0; idx < sum; ++idx) 6 combi[idx + 1] = idx; 7 while (true) { 8 std::set<u8> unionSet; 9 if (unionValsByCombi(sum, combi, pGrp, unionSet)) {10 u8 compSet[10] = {0};11 for (std::set<u8>::iterator it = valSet.begin(); it != valSet.end(); ++it)12 if (unionSet.find(*it) == unionSet.end()) {13 compSet[0] += 1;14 compSet[compSet[0]] = *it;15 }16 combi[0] = sum; // for soon calling inSet properly17 u8 cells[10] = {0};18 for (u8 pos = 0; pos < pGrp[0]; ++pos) {19 if (!inSet(pos, combi)) {20 cells[0] += 1;21 cells[cells[0]] = pos;22 }23 }24 combi[0] = pGrp[0]; //back again25 bool shrunken = false;26 for (u8 idx = 1; idx <= cells[0]; ++idx) {27 u8 pos = pGrp[cells[idx] + 1];28 for (u8 inn = 1; inn <= m_seqCell[pos].candidates[0];) {29 u8 val = m_seqCell[pos].candidates[inn];30 if (inSet(val, compSet))31 ++inn;32 else {33 shrunken = true;34 removeVal(m_seqCell[pos].candidates, val);35 printf("3GW: %d shrunken out of [%d,%d]\n", (int)val, (int)pos / 9 + 1, (int)pos % 9 + 1);36 }37 }38 }39 if (shrunken)40 return RET_SHRUNKEN;41 }42 if (!move2NextCombi(sum, combi))43 break;44 }45 return RET_PENDING;46 }
新增 unionValsByCombi 接口实现
1 bool CQuizDealer::unionValsByCombi(u8 sum, u8* pCombi, u8* pGrp, std::set<u8>& unionSet) 2 { 3 for (u8 idx = 1; idx <= sum; ++idx) { 4 u8 pos = pGrp[pCombi[idx] + 1]; 5 u8 valSum = m_seqCell[pos].candidates[0]; 6 if (valSum > sum) 7 return false; 8 for (u8 vidx = 1; vidx <= valSum; ++vidx) { 9 u8 val = m_seqCell[pos].candidates[vidx];10 unionSet.insert(val);11 }12 if (unionSet.size() > sum)13 return false;14 }15 return (unionSet.size() == sum);16 }
其他小修改
// 1.0 2021/9/20// 2.0 2021/10/2// 2.1 2021/10/4// 2.2 2021/10/10// 2.3 2021/10/17#define STR_VER "Sudoku Solver 2.4 2021/10/19 by readalps\n\n"void showOrderList(){ printf(STR_VER); printf("Order List:\n"); printf("load-quiz <file>: load quiz from file\n"); printf("show: show quiz info\n"); printf("mode [1|2|0]: query or change working mode\n"); printf("step: step forward\n"); printf("run: run till the end or a new solution met\n"); printf("runtil <steps>: run till certain steps run\n"); printf("bye: quit\n");}void dealOrder(std::string& strOrder){ std::string strEx; if ("bye" == strOrder) setQuit(); else if (matchPrefixEx(strOrder, "load-quiz ", strEx)) CQuizDealer::instance()->loadQuiz(strEx); else if ("show" == strOrder) CQuizDealer::instance()->showQuiz(); else if (matchPrefixEx(strOrder, "mode", strEx)) CQuizDealer::instance()->mode(strEx); else if ("step" == strOrder) CQuizDealer::instance()->step(); else if ("run" == strOrder) CQuizDealer::instance()->run(); else if (matchPrefixEx(strOrder, "runtil ", strEx)) { ulong tilsteps = strtoul(strEx.c_str(), 0, 10); CQuizDealer::instance()->run(tilsteps); } else showOrderList();}
实例分析
“最难”数独题
继续以 SudokuSolver 1.0:用C++实现的数独解题程序 【二】 里试验过的“最难”数独题为例做分析。
D:\read\num\Release>sudoku.exeOrder please:Sudoku Solver 2.4 2021/10/19 by readalpsOrder List:load-quiz <file>: load quiz from fileshow: show quiz infomode [1|2|0]: query or change working modestep: step forwardrun: run till the end or a new solution metruntil <steps>: run till certain steps runbye: quitOrder please:load-quiz s.txtQuiz loaded.Order please:run...1014) col 8 complete shrunken by group1017) Guess [1,6] level 8 at 1 out of 21018) row 3 complete shrunken by group1020) row 3 complete shrunken by group1GW: 8 shrunken out of [2,7]1022) row 2 incomplete shrunken by group1023) Guess [1,8] level 9 at 1 out of 21026) row 9 complete shrunken by group1028) col 6 complete shrunken by group1031) Guess [2,5] level 10 at 1 out of 21034) shrinking 4 from [6,3] went wrong1035) Forward guess [2,5] level 10 at 2 out of 2812 753 649943 682 175675 491 283154 237 896369 845 721287 169 534521 974 368438 526 917796 318 452Done [steps:1040, solution sum:1].Run time: 430 milliseconds; steps: 1040, solution sum: 1.Order please:
第二次 run 命令的输出信息为:
run ...1GW: 2 shrunken out of [5,1]1GW: 9 shrunken out of [5,1]1GW: 2 shrunken out of [5,2]1GW: 2 shrunken out of [5,4]1GW: 9 shrunken out of [5,4]1GW: 2 shrunken out of [5,8]1GW: 9 shrunken out of [5,8]1698) row 5 incomplete shrunken by group1699) Guess [1,3] level 6 at 1 out of 21703) row 1 complete shrunken by group1705) row 2 complete shrunken by group1707) row 4 complete shrunken by group1707) shrinking 9 from blk[5,1] went wrong1708) Forward guess [1,3] level 6 at 2 out of 21709) shrinking 2 from [4,9] went wrong1710) No more solution (solution sum is 1).809 000 306503 600 800076 090 250054 007 120002 045 789000 100 635001 000 568008 500 910090 000 400Invalid quiz [steps:1710] - no more solution (solution sum is 1)Run time: 265 milliseconds; steps: 1710, solution sum: 1.Order please:
从输出的完整信息看,不再有“ply”信息,说明求解过程中只用到了 grp 算法,而没有用到 ply 算法。
第一次 run 命令走了 1040 步,求得一个解,用时约 430 毫秒;第二次 run 命令用了约 265 毫秒得出结论此 quiz 只有一个解,两次 run 命令共走了 1710 步。
退出程序并重新进入交互,这次显式仅用 grp 算法模式求解:
Order please:byeD:\read\num\Release>sudoku.exeOrder please:modeWorking mode:0 (1:grp-only; 2:ply-only; other:both grp and ply)Order please:mode 1Working mode:1 (1:grp-only; 2:ply-only; other:both grp and ply)Order please:load-quiz s.txtQuiz loaded.Order please:run...1GW: 8 shrunken out of [2,7]1022) row 2 incomplete shrunken by group1023) Guess [1,8] level 9 at 1 out of 21026) row 9 complete shrunken by group1028) col 6 complete shrunken by group1031) Guess [2,5] level 10 at 1 out of 21034) shrinking 4 from [6,3] went wrong1035) Forward guess [2,5] level 10 at 2 out of 2812 753 649943 682 175675 491 283154 237 896369 845 721287 169 534521 974 368438 526 917796 318 452Done [steps:1040, solution sum:1].Run time: 421 milliseconds; steps: 1040, solution sum: 1.Order please:run...1GW: 9 shrunken out of [5,8]1698) row 5 incomplete shrunken by group1699) Guess [1,3] level 6 at 1 out of 21703) row 1 complete shrunken by group1705) row 2 complete shrunken by group1707) row 4 complete shrunken by group1707) shrinking 9 from blk[5,1] went wrong1708) Forward guess [1,3] level 6 at 2 out of 21709) shrinking 2 from [4,9] went wrong1710) No more solution (solution sum is 1).809 000 306503 600 800076 090 250054 007 120002 045 789000 100 635001 000 568008 500 910090 000 400Invalid quiz [steps:1710] - no more solution (solution sum is 1)Run time: 265 milliseconds; steps: 1710, solution sum: 1.Order please:byeD:\read\num\Release>
从输出信息看,除了第一次 run 命令用时比之前略微减少(从 430 减为 421)之外,其他信息完全一致。
再看一下显式仅用 ply 算法模式求解的输出信息:
D:\read\num\Release>sudoku.exeOrder please:load-quiz s.txtQuiz loaded.Order please:show800 000 000003 600 000070 090 200050 007 000000 045 700000 100 030001 000 068008 500 010090 000 400Order please:mode 2Working mode:2 (1:grp-only; 2:ply-only; other:both grp and ply)Order please:run...1054) col 6 shrunken ply-1 by vblk 2[2,8]: 5 7 shrunken to 7 worked by col-ply1.1056) col 8 shrunken ply-1 by vblk 11059) Guess [2,5] level 10 at 1 out of 21063) shrinking 8 from [4,7] went wrong1064) Forward guess [2,5] level 10 at 2 out of 2812 753 649943 682 175675 491 283154 237 896369 845 721287 169 534521 974 368438 526 917796 318 452Done [steps:1069, solution sum:1].Run time: 468 milliseconds; steps: 1069, solution sum: 1.Order please:run...1335) col 8 shrunken ply-2 by vblk 2[4,9]: 1 2 4 6 9 shrunken to 1 4 6 9 worked by col-ply2.[5,9]: 1 2 6 9 shrunken to 1 6 9 worked by col-ply2.incomplete shrink met, filter again1339) Guess [1,3] level 8 at 1 out of 2...2100) row 8 shrunken ply-1 by blk 2[8,2]: 2 3 4 shrunken to 4 worked by row-ply2.2102) row 8 shrunken ply-2 by blk 3[6,1]: 2 7 9 shrunken to 7 worked by row-ply2.[6,3]: 2 4 7 9 shrunken to 4 7 worked by row-ply2.2104) row 6 shrunken ply-2 by blk 22104) shrinking 2 from [8,1] went wrong2105) No more solution (solution sum is 1).800 000 306003 600 800476 893 251350 067 100160 345 700704 100 635201 000 568048 506 910695 000 400Invalid quiz [steps:2105] - no more solution (solution sum is 1)Run time: 493 milliseconds; steps: 2105, solution sum: 1.Order please:
可以看出,仅用 ply 算法求解,比起仅用 grp 算法求解,用时和步数都略有增加。第二次 run 命令的输出里有几次如下的信息输出:
incomplete shrink met, filter again
这正好对应 用C++实现的数独解题程序 SudokuSolver 2.1 及实例分析 里所言的:
这样的两次关联收缩,倘若第一次不完全收缩发生在第五轮的 col-ply 筛查阶段,就会导致第二次的完全收缩接续不上,进而多加一次猜测行为。这是一个可改进之处
。2.2 版本改进之后一直没有碰到这种情形,直到这里仅用 ply 算法求解时才碰到。另一道数独题
这一道据说也挺有难度:
005 300 000800 000 020070 010 500400 005 300010 070 006003 200 080060 500 009004 000 030000 009 700
把这 9 行数字放到一个文本文件(比如 D:\read\num\Release\s.txt)的头部位置。这次不对输出做删节处理,呈现完整的两次 run 命令输出:
D:\read\num\Release>sudoku.exeOrder please:load-quiz s.txtQuiz loaded.Order please:run2) row 2 complete shrunken by group4) row 5 complete shrunken by group2GW: 2 shrunken out of [4,3]2GW: 8 shrunken out of [4,3]2GW: 9 shrunken out of [4,3]2GW: 5 shrunken out of [6,1]2GW: 9 shrunken out of [6,1]CelSet: [4,3] [6,1] ValSet: 6 76) blk 4 incomplete shrunken by group7) Guess [6,2] level 1 at 1 out of 28) row 5 complete shrunken by group11) Guess [4,3] level 2 at 1 out of 213) col 3 complete shrunken by group16) Guess [2,3] level 3 at 1 out of 218) Guess [3,3] level 4 at 1 out of 224) col 8 complete shrunken by group28) row 3 complete shrunken by group30) row 1 complete shrunken by group32) row 1 complete shrunken by group35) shrinking 1 from [9,1] went wrong36) Forward guess [3,3] level 4 at 2 out of 22GW: 1 shrunken out of [1,8]2GW: 4 shrunken out of [1,8]2GW: 6 shrunken out of [1,8]2GW: 1 shrunken out of [4,8]CelSet: [1,8] [4,8] ValSet: 7 937) col 8 incomplete shrunken by group38) Guess [1,1] level 5 at 1 out of 240) shrinking 9 from [2,4] went wrong41) Forward guess [1,1] level 5 at 2 out of 243) Guess [1,2] level 6 at 1 out of 246) row 2 complete shrunken by group48) row 3 complete shrunken by group50) row 4 complete shrunken by group52) row 4 complete shrunken by group54) shrinking 8 from [9,4] went wrong55) Forward guess [1,2] level 6 at 2 out of 257) row 3 complete shrunken by group59) row 8 complete shrunken by group1GW: 8 shrunken out of [9,4]1GW: 2 shrunken out of [9,5]1GW: 8 shrunken out of [9,5]1GW: 2 shrunken out of [9,9]1GW: 8 shrunken out of [9,9]61) row 9 incomplete shrunken by group62) Guess [1,8] level 7 at 1 out of 264) shrinking 9 from [1,5] went wrong65) Forward guess [1,8] level 7 at 2 out of 267) row 2 complete shrunken by group69) row 4 complete shrunken by group71) row 6 complete shrunken by group73) col 4 complete shrunken by group1GW: 4 shrunken out of [2,9]75) blk 3 incomplete shrunken by group76) Guess [1,5] level 8 at 1 out of 278) row 1 complete shrunken by group81) Guess [1,7] level 9 at 1 out of 284) Guess [2,6] level 10 at 1 out of 287) row 9 complete shrunken by group89) col 4 complete shrunken by group92) Guess [4,2] level 11 at 1 out of 292) shrinking 8 from [8,7] went wrong93) Forward guess [4,2] level 11 at 2 out of 293) shrinking 5 from [8,1] went wrong94) Upward guess [2,6] level 10 at 2 out of 295) shrinking 5 from [9,9] went wrong96) Upward guess [1,7] level 9 at 2 out of 296) shrinking 4 from blk[6,9] went wrong97) Upward guess [1,5] level 8 at 2 out of 297) shrinking 7 from [2,9] went wrong98) Upward guess [2,3] level 3 at 2 out of 2102) row 3 complete shrunken by group105) Guess [1,9] level 4 at 1 out of 2106) row 4 complete shrunken by group108) col 8 complete shrunken by group2GW: 6 shrunken out of [8,4]2GW: 8 shrunken out of [8,4]2GW: 2 shrunken out of [8,6]2GW: 6 shrunken out of [8,6]2GW: 8 shrunken out of [8,6]CelSet: [8,4] [8,6] ValSet: 1 7110) row 8 incomplete shrunken by group111) Guess [1,8] level 5 at 1 out of 2117) shrinking 2 from [4,2] went wrong118) Forward guess [1,8] level 5 at 2 out of 2120) shrinking 8 from [9,9] went wrong121) Upward guess [1,9] level 4 at 2 out of 2123) Guess [1,7] level 5 at 1 out of 2124) col 8 complete shrunken by group2GW: 4 shrunken out of [2,4]2GW: 1 shrunken out of [8,4]2GW: 8 shrunken out of [8,4]CelSet: [2,4] [8,4] ValSet: 6 7126) col 4 incomplete shrunken by group127) Guess [1,5] level 6 at 1 out of 2145 327 698839 654 127672 918 543496 185 372218 473 956753 296 481367 542 819984 761 235521 839 764Done [steps:131, solution sum:1].Run time: 46 milliseconds; steps: 131, solution sum: 1.Order please:run132) Forward guess [1,5] level 6 at 2 out of 21GW: 4 shrunken out of [2,6]135) row 2 incomplete shrunken by group136) Guess [2,4] level 7 at 1 out of 2138) row 3 complete shrunken by group139) shrinking 8 from blk[8,7] went wrong140) Forward guess [2,4] level 7 at 2 out of 2142) row 3 complete shrunken by group143) shrinking 8 from blk[8,7] went wrong144) Upward guess [1,7] level 5 at 2 out of 2146) shrinking 8 from [9,4] went wrong147) Upward guess [4,3] level 2 at 2 out of 2149) row 6 complete shrunken by group151) col 8 complete shrunken by group154) Guess [4,8] level 3 at 1 out of 2157) row 6 complete shrunken by group1GW: 4 shrunken out of [1,7]1GW: 4 shrunken out of [2,7]159) col 7 incomplete shrunken by group160) Guess [3,1] level 4 at 1 out of 2163) shrinking 8 from [9,5] went wrong164) Forward guess [3,1] level 4 at 2 out of 2165) row 2 complete shrunken by group167) row 7 complete shrunken by group169) row 9 complete shrunken by group172) Guess [2,2] level 5 at 1 out of 2174) Guess [1,2] level 6 at 1 out of 2176) row 3 complete shrunken by group178) col 6 complete shrunken by group180) row 5 complete shrunken by group183) row 8 complete shrunken by group184) shrinking 2 from [8,7] went wrong185) Forward guess [1,2] level 6 at 2 out of 2187) row 2 complete shrunken by group189) shrinking 5 from [9,1] went wrong190) Upward guess [2,2] level 5 at 2 out of 2193) row 1 complete shrunken by group194) shrinking 6 from [8,6] went wrong195) Upward guess [4,8] level 3 at 2 out of 2196) row 6 complete shrunken by group199) Guess [3,8] level 4 at 1 out of 22GW: 1 shrunken out of [1,7]2GW: 8 shrunken out of [1,7]2GW: 1 shrunken out of [2,7]CelSet: [1,7] [2,7] ValSet: 6 9201) col 7 incomplete shrunken by group202) Guess [1,9] level 5 at 1 out of 2203) shrinking 1 from [4,4] went wrong204) Forward guess [1,9] level 5 at 2 out of 2206) shrinking 1 from [4,4] went wrong207) Upward guess [3,8] level 4 at 2 out of 2208) col 3 complete shrunken by group210) col 7 complete shrunken by group212) col 6 complete shrunken by group214) blk 1 complete shrunken by group1GW: 1 shrunken out of [7,7]1GW: 4 shrunken out of [7,7]1GW: 1 shrunken out of [8,9]1GW: 1 shrunken out of [9,9]1GW: 4 shrunken out of [9,9]216) blk 9 incomplete shrunken by group217) Guess [1,9] level 5 at 1 out of 2218) col 2 complete shrunken by group221) shrinking 9 from [5,3] went wrong222) Forward guess [1,9] level 5 at 2 out of 2223) col 7 complete shrunken by group225) col 7 complete shrunken by group230) shrinking 8 from [4,4] went wrong231) Upward guess [6,2] level 1 at 2 out of 2232) row 6 complete shrunken by group234) row 5 complete shrunken by group236) row 6 complete shrunken by group239) row 8 complete shrunken by group241) row 9 complete shrunken by group243) col 3 complete shrunken by group245) blk 9 complete shrunken by group248) Guess [1,2] level 2 at 1 out of 2251) shrinking 7 from [1,9] went wrong252) Forward guess [1,2] level 2 at 2 out of 2254) row 3 complete shrunken by group257) Guess [2,3] level 3 at 1 out of 21GW: 2 shrunken out of [9,1]1GW: 8 shrunken out of [9,4]1GW: 2 shrunken out of [9,5]1GW: 8 shrunken out of [9,5]1GW: 2 shrunken out of [9,9]1GW: 8 shrunken out of [9,9]258) row 9 incomplete shrunken by group259) Guess [1,1] level 4 at 1 out of 2260) shrinking 6 from [2,4] went wrong261) Forward guess [1,1] level 4 at 2 out of 23GW: 2 shrunken out of [7,5]3GW: 8 shrunken out of [7,5]263) col 5 incomplete shrunken by group264) Guess [2,7] level 5 at 1 out of 2266) shrinking 2 from [7,7] went wrong267) Forward guess [2,7] level 5 at 2 out of 2268) row 1 complete shrunken by group271) row 1 complete shrunken by group273) row 5 complete shrunken by group3GW: shrink went wrong275) row 7 shrink by group went WRONG276) Upward guess [2,3] level 3 at 2 out of 2280) row 5 complete shrunken by group282) col 7 complete shrunken by group283) shrinking 6 from [2,4] went wrong284) No more solution (solution sum is 1).145 300 900839 050 127672 018 543426 005 371518 473 296793 261 485067 500 819954 000 632081 609 750Invalid quiz [steps:284] - no more solution (solution sum is 1)Run time: 63 milliseconds; steps: 284, solution sum: 1.Order please:byeD:\read\num\Release>
可以看到,这个 quiz 的求解过程,出现的最深猜测级别为 11 级:
92) Guess [4,2] level 11 at 1 out of 2
仅比前面那个 quiz 少一级。但从用时和步数看,这个 quiz 要容易不少。