用C语言编程解谜：探索数独的生成与解决

需积分: 9 183 浏览量更新于2024-07-22 收藏 4.46MB PDF 举报

"Sudoku Programming with C(Apress,2015)" 是一本关于使用C语言编写程序解决和生成数独谜题的书籍。作者通过本书教你如何创建自己的数独经典和武士难题集，揭示数独背后的逻辑和生成方法。本书详细讲解了数独编程的相关知识点，包括但不限于： 1. **模型构建**：第一章介绍了如何用C语言来建模一个数独谜题，这涉及到理解数独的基本规则和结构，以及如何用编程语言来表示这些规则。 2. **解题策略**：从第二章开始，书中逐步深入到各种解题策略，如基于单元格的唯一性、裸露策略（Naked Strategies）、隐藏策略（Hidden Strategies）等，这些都是解决数独问题的关键步骤。 3. **算法实现**：从第三章到第十六章，每章都专注于一种或几种解题或生成策略的实现。例如，"Unique"（唯一性）的实现，"Naked"（裸露）和"Hidden"（隐藏）策略涉及的逻辑推理，"Box-Line"（宫线）、"Pointing Line"（指向线）、"Lines"（线策略）、"Y-wing"（Y型翼）、"XY-chain"（XY链）等复杂策略的编程实现，这些都是高级数独解决技巧。 4. **回溯法**：第十三章介绍了回溯法，这是一种在解决无法直接得出答案时，通过试错来寻找解决方案的通用算法，对于解决复杂数独问题非常有效。 5. **大量谜题求解**：第十四章讲述了如何处理和解决成千上万的数独谜题，这涉及到优化解题效率和处理大量数据的方法。 6. **生成数独**：第十五章探讨了如何生成具有特定特性的数独谜题，这不仅包括随机生成，也包括设计出具有挑战性和趣味性的数独。 7. **统计与分析**：第十六章涉及谜题的统计和更多谜题的生成，可能涵盖了难度评估、解题时间分析等内容，有助于理解数独谜题的多样性和挑战性。通过这本书，读者不仅可以学习到C语言编程技能，还能深入理解数独游戏背后的数学逻辑和算法思维。无论是对数独爱好者还是对编程有兴趣的人，都能从中学到有价值的知识。

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)

www.it-ebooks.info

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

www.it-ebooks.info

剩余284页未读，继续阅读

vanridin

粉丝: 108
资源: 1188

用C语言编程解谜：探索数独的生成与解决

VC++2015资源文件压缩包

Sudoku Programming With C

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

用c语言代码写数独游戏

sudoku游戏matlab

Valid Sudoku

最新资源