数独难题的笔纸算法与Scala多线程实现

需积分: 11 14 浏览量更新于2024-09-10 收藏 616KB PDF 举报

本文档探讨了"A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles"，一种经典的数独解谜方法，由J.F.Crook提出。数独作为一种在全球范围内广受欢迎的智力游戏，其吸引力在于尽管解决方案存在，但凭借纸笔和逻辑推理解决它仍然具有挑战性。数独的核心在于其规则，即每个3x3宫格、行、列中都必须包含1-9的数字，且每行、每列和每个宫格内的数字都不重复。算法的核心是基于回溯的树形搜索。解决者从空白的格子开始，尝试填入可能的数字，形成一个递归过程。如果某一步填入的数字导致了冲突（如重复的数字），就退回一步，尝试其他数字。这个过程会不断重复，直到找到所有空格都填满且满足所有规则的唯一解。在现代技术背景下，虽然个人电脑可以轻松解决数独，但许多人更倾向于通过手写和纸质版进行挑战。根据Herzberg和Murty（2007）的观点，这有两个主要原因：首先，数独提供了适度的挑战，对不同水平的思考者都有吸引力；其次，通过手动扫描和填充，解谜者可以直观地看到进展，并从中获得成就感和鼓励，这种过程本身就是一种乐趣。文章作者开发了一个使用纸笔方法的算法，尽管在实际应用中，用C语言实现可能会更为直接和高效。然而，将同样的算法移植到Scala语言并利用多线程技术，无疑会带来额外的技术挑战，因为它涉及并行处理和优化，从而提高计算效率。这对于学习和理解并发编程以及如何在实际问题中应用算法思想具有一定的价值。这篇论文不仅介绍了数独的解决策略，还强调了传统方式与现代技术结合的乐趣，同时也提供了一种潜在的教学资源，让读者能够理解和实践基于回溯的算法在解决复杂逻辑问题时的应用。

A Pencil-and-Paper

Algorithm for Solving

Sudoku Puzzles

J. F. Crook

e puzzle Sudoku has become the pas-

sion of many people the world over in

the past few years. The interesting fact

about Sudoku is that it is a trivial puzzle

to solve. The reason it is trivial to solve

is that an algorithm exis ts for Sudoku solutions.

The algorithm is a tree-based search algorithm

based on backtracking in a tre e until a solution is

found.

If all a person needs to do is sit down at their

personal computer, punch in the numbers given in

the puzzle, and then watch a computer program

compute the solution, we can reasonably ask why

a pers on would bother to struggle to solve Sudoku

puzzles. The reason is that people enjoy strug-

gling with pencil and paper to work out Sudoku

solutions. Herzberg and Murty (2007, p. 716) give

two reasons for the enjoyment of this struggle:

First, it i s suﬃciently diﬃcult to pose a serious

mental challenge for anyone attempting to do the

puzzle. Secondly, simply by scanning rows and

columns, it is easy to enter the “missing colors”,

and this gives the solver some encouragement to

persist.

This paper develops an algorithm for solving

any Sudoku puzzle by pencil and paper, especially

the ones classiﬁed as diaboli cal.

Deﬁnition of the Sudoku Board

Sudoku is played on a 9 × 9 board. There are

eighty-one cells on the board, which is broken

J. F. Crook is professor emeritus of computer science,

Winthrop University, Rock Hill, SC. H is email address is

crookj@winthrop.edu.

I thank John Hohn, Kathryn Cooper, David Gill, and

Libby Neely for reading my paper. I also thank Loretta

Nethercot for giving me my ﬁrst two Sudoku books—on

Christmas Day, 2005, and on my seventieth birthday in

2007.

down into nine 3 × 3

subboards that do not over-

lap. We call these subboards boxes and number

them from 1 to 9 in typewriter order beginning

in the upper left-hand corner of the board, as

displayed in Figure 1.

The notation for referring to a par ticular cell

on the board is to give the row numb er followed

by the column number. For example, the notation

c (6, 7)—where c denotes cell—denotes the cell at

the intersection of row 6 and column 7.

The theory we develop in the next section uses

the widely known concept of matching numbers

across cells. Various authors, as suits their whim,

name matching numbers diﬀerently. For example,

Sheldon (2006, p. xiv) names them partnerships,

whereas Mepham (2005, p. 9) names the con-

cept number sharing. Here, we will use the name

preemptive sets, which is more precise from a

mathematical point of view. The theory developed

here applies to Sudoku boards of all sizes .

Sudoku boards can be classiﬁed into regular and non-

regular boards. The formula for regular Sudoku boards

is: Let m denote the width and height of a Sudoku sub-

board, where m ≥ 2. Then the width and height of a

regular Sudoku board is m

. The sizes of regular sub-

boards and boards are given for a few values of m in the

following table:

Subboard Width Board Width Number of Cells

and Height and Height on the Board

m m

× m

2 4 16

3 9 81

4 16 256

5 25 625

6 36 1296

The most common nonregular Sudoku board is the

6 × 6, which consists of six nonoverlapping 2 × 3 sub-

boards. The newspaper USA Today publishes 6 × 6

puzzles regularly.

460 Notices of the AMS Volume 56, Number 4

下载后可阅读完整内容，剩余8页未读，立即下载

mynameisi

粉丝: 0
资源: 5

数独难题的笔纸算法与Scala多线程实现

烹饪分类信息编辑

最新资源

数独难题的笔纸算法与Scala多线程实现

pay-to-sudoku, 用零知识支付支付一个数独游戏的解决方案.zip

Pencil-1.0-4-win32

界面设计工具Pencil-1.2.0.win32.installer.exe

帮我编写一个linux shell脚本用于利用for循环将paper pencil pen输出在屏幕上

解释一下这段代码 <button class="btn btn-success"> </button> <button class="btn btn-info"> </button> <button class="btn btn-warning"> </button> <button class="btn btn-danger"> </button>

1．用Java编写一个程序，其中线程1首先用Pen写字，然后用Pencil写字；线程2首先用Pencil写字，然后用Pen写字；编写一个因为线程1等待Pencil，线程2等待Pen而造成死锁的例子，并提出解决方法。

烹饪分类信息编辑

程序主函数:初始化一个CashRegister对象，并将三张购物小票的内容保存到对应的变量当中，并调用CashRegister对象中的对应方法进行小票字符串的处理及结果的输出。

二代pencil无法充电

Apple Pencil无线充电原理技术

最新资源

解释一下这段代码

<button class="btn btn-success"> </button> <button class="btn btn-info"> </button> <button class="btn btn-warning"> </button> <button class="btn btn-danger"> </button>