解密数独编程：使用C语言实现解题与生成

需积分: 10 164 浏览量更新于2024-07-18 收藏 4.27MB PDF 举报

"Sudoku Programming With C" 本书"数独编程用C语言"是关于如何用C语言编写程序解决和生成数独谜题的实用指南。它不仅教你如何编写自己的数独经典和武士难题集，还会让你对那些看似复杂的报纸上的数独谜题产生新的认识，你会发现它们其实并不那么难。数独之所以吸引人，是因为它们能测试我们识别和解释模式的能力。然而，这些提示是如何生成的？那些近乎对称的配置从何而来？作者在互联网上寻找答案时发现，有很多网站解释如何解决数独，但几乎没有一个解释如何创建它们。同样，尽管有许多用于玩数独的应用程序，但很少有说明它们的工作原理。因此，作者决定自己开发应用程序，并将代码公开，以便其他人可以使用和修改。为了让尽可能多的人理解，他选择了使用“古老的”C语言来编写。书中的内容包括所有解题策略的解释以及实现它们的代码。编写求解器应用程序比生成器更具有挑战性，因为它需要分别设计和实现每种策略。作者希望包含一个解题程序，能够列出解决特定谜题所需的策略，并且能够检查一个谜题是否可以通过分析方法而非猜测来解决。书中提供了生成器和求解器的完整代码列表，以及所有C模块的解释，包括逐步指导和示例。章节涵盖了从基础模型到高级策略，如“唯一候选数”、“裸露数”、“隐藏数”、“盒线”、“指向线”、“线策略”、“Y翼”、“XY链”、“矩形”和“回溯”等。此外，还有解决数千个谜题的方法和生成数独的技巧，以及谜题统计和更多谜题的讨论。通过这本书，无论你是编程新手还是经验丰富的程序员，都可以深入理解数独背后的逻辑和算法。你将能够立即开始生成自己的数独谜题，并逐步学习和掌握各种解题技术，从而提升你的逻辑思维能力。

Chapter 2 ■ the StrategieS

Usage of Level 0 Strategies

When removing a candidate from a cell, it could be that it was one of only two candidates in that cell. If that

is the case, by removing it, you leave the cell with a single candidate, which means that the naked single

strategy applies. For example, if (2,7) contains two candidates, 1 and 3, and you remove the 3, it is clear that

1 must solve the cell.

It could also be that the candidate you have removed was one of only two candidates for a particular

number in a unit. In that case, the unique strategy applies to the remaining candidate. For example, if you

remove a 3 from cell (2,7), it could be that only one candidate 3 is left in column 7, say, in (8,7). In that

case, 3 must solve (8,7), otherwise there wouldn’t be any 3 at all in column 7.

Obviously, you must do a cleanup whenever you solve a cell. Otherwise, there is a good chance that you

keep considering as possible some candidates that are not.

All in all, it makes sense to apply naked single and unique whenever you remove a candidate, followed

by a cleanup if naked single or unique solves a cell. This often results in a chain of removals that can

completely solve easy Sudokus. (See, for example, Figure 2-1).

Figure 2-1. An easy Sudoku

And following is the beginning of the Solver’s log:

unique_unit: 5 in (4,0) is unique within the column

unique_unit: removed 3 from (4,0)

unique_unit: removed 6 from (4,0)

unique_unit: removed 8 from (4,0)

unique_unit: removed 9 from (4,0)

cleanup_unit [row of (4,0)]: removed 5 in (4,3)

Chapter 2 ■ the StrategieS

All 5s of box 6 are within row 7. Therefore, 5 must solve either (7,0) or (7,2). Otherwise, there would

be no 5 in box 6. As a result, you can remove the 5s from (7,7) and (7,8) because there cannot be more

than one 5 in row 7, and you know that either (7,0) or (7,2) is a 5.

This strategy is in a sense symmetrical to the box-line strategy that I described in the previous section.

Both strategies rely on a candidate that appears in the three-cell intersection of a box with a line, but box-

line lets you remove some candidates from the box when the candidates do not appear anywhere else in the

intersecting line, while pointing line lets you remove some candidates from the line when the candidates do

not appear anywhere else in the intersecting box.

Level 2 Strategies

Level 2 strategies are more complex than level 1 strategies. The patterns of candidates that let you apply

the strategies are not easy to identify. The strategies are naked triple, hidden triple, lines-2, naked quad, and

Y-wing.

The Strategies Naked Triple and Naked Quad

These are extensions of the naked pair strategy to triplets and quadruplets of candidates.

Naked triple: if three cells in the same unit only contain the same three candidates, it means that one

of those candidates will solve one of the three cells, another candidate will solve a second cell, and the third

candidate will solve the remaining cell. Therefore, you can remove the same candidates from all other cells

of the unit.

Naked quad: if four cells in the same unit only contain the same four candidates, it means that one

of those candidates will solve one of the four cells, another candidate will solve a second cell, yet another

candidate will solve a third cell, and the fourth candidate will solve the remaining cell. Therefore, you can

remove the same candidates from all other cells of the unit.

Now, theoretically, you could have a naked strategy with more than four cells, but they are so unlikely

that it isn’t worth considering them.

The Strategy Hidden Triple

This is an extension of the hidden pair strategy to triplets of candidates. If three candidates only appear in

three cells of a unit, it means that one of those candidates will solve one of the three cells, another candidate

will solve a second cell, and the third candidate will solve the remaining cell. Therefore, you can remove all

other candidates in the three cells.

Figure 2-5. A pointing line configuration

剩余284页未读，继续阅读

kernelkoder

粉丝: 57
资源: 317

解密数独编程：使用C语言实现解题与生成

SudokuProgrammingWithC.pdf 英文原版

数独sudoku

数独 sudoku

sudoku c语言

Error: Couldn't copy [D:\sudoku\sudu\seg0\d820.dat] to [D:\sudoku\out\production\sudoku1\sudu\seg0\d820.dat]

Resource compiler: Error: Couldn't copy [D:\sudoku\sudu\seg0\dae0.dat] to [D:\sudoku\out\production\sudoku1\sudu\seg0\dae0.dat]

sudoku vue

sudoku游戏matlab

Valid Sudoku

最新资源