具有一些高级功能的Sudoku程序（译文）

By robot-v1.0

本文链接 https://www.kyfws.com/games/a-sudoku-program-with-some-advanced-features-zh/

版权声明 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

- 10 分钟阅读 - 4857 个词 阅读量 0

具有一些高级功能的Sudoku程序（译文）

原文地址：https://www.codeproject.com/Articles/865143/A-Sudoku-program-with-some-advanced-features

原文作者：Jacques Fournier

译文由本站 robot-v1.0 翻译

前言

Sudoku is a program built in C# with a WPF user interface.

Sudoku是使用WPF用户界面在C#中构建的程序.

[Image 1

](http://www.codeproject.com/KB/Articles/865143/SudokuWithSym.jpg)

介绍(Introduction)

Sudoku 是使用WPF用户界面在C#中构建的程序.它可以轻松,中度或高级生成9x9或16x16板.几年前,我对它进行了编程,最后决定发布它,因为它实现了其他帖子中没有的某些功能.(is a program built in C# with a WPF user interface. It can generate 9x9 or 16x16 boards at easy, medium or advanced level. I programmed it years ago and finally decided to publish it seeing that it implements some functions not found in the other postings.)

特征(Features)

该数独程序具有以下特点:(This sudoku program features:)

  • 具有不同难度级别的9x9或16x16板(9x9 or 16x16 boards with different difficulty levels)
  • 任何9x9或16x16数独谜题的分辨率(Resolution of any 9x9 or 16x16 Sudoku puzzle)
  • 可自定义的字体和颜色(Customizable fonts and colors)
  • 可自定义的符号,用于表示值(数字,字母或符号)(Customizable symbols used to represent values (numbers, letters or symbols))
  • 输入模式的选择:单元格切换或值选择器(Choices of input modes: cell toggle or value picker)
  • 输入值模式,仅接受有效值或接受任何值(Input value modes which accepts only valid values or accepts any values)
  • 打印数独板(当前或成批)(Printing of sudoku boards (the current one or in batch))
  • 设计自己的数独(设计模式)(Designing your own sudoku (design mode))
  • 保存或加载数独板(Saving or loading of a sudoku board)
  • 撤消/重做功能(Undo / redo functions)
  • 不同种类的提示(Different kinds of hints)
  • 等等.(Etc.) Image1

数独板使用符号代替数字(Sudoku board using symbols instead of numbers)

Image 3

使用字母而非数字的16x16数独板(16x16 Sudoku board using letters instead of numbers)

版本控制(Versioning)

|版本2.01(Version 2.01)|原始发布版本.(Original posted version.)

提供的演示(Demo Provided)

提供的演示是带有WPF接口的C#中的sudoku程序.(The provided demo is the sudoku program in C# with the WPF interface.)

资料来源(Sources Provided)

除了提供的演示的源代码之外,我还包括使用Windows Forms编写的该程序的早期版本.不支持后一个版本.(In addition to the source of the provided demo, I also include a prior version of this program written using Windows Forms. This latter version is not supported.)

需要改进什么？(What Needs to be Improved?)

-能够为木板添加注释会很好.(- It would be nice to be able to annotate the board.) -我在其他数独游戏中看到了有趣的输入法,可以将其添加到此版本中.(- I saw interesting input methods in other Sudoku games which can be added to this version.) -关卡难度可能会更微妙.(- The level difficulty can be more subtle.) -欢迎向游戏中添加帮助文件.(- Adding a help file to the game would be welcome.)

来源描述(Source Description)

该项目中包括的主要类是:(The main classes included in the project are:) 发动机舱(Engine Classes)

  • CellPos(CellPos):单元格位置(x,y)(: Cell position (x,y))

  • 南极板(SudBoard):实现数独板的抽象类(: Abstract class implementing the sudoku board)

  • SudBoard9(SudBoard9):9x9板的SudBoard实施(: SudBoard implementation for a 9x9 board)

  • SudBoard16(SudBoard16):SudBoard实施16x16特定功能(: SudBoard implementation for 16x16 specific functions)

  • SudBoardGenerator(SudBoardGenerator):同步或异步生成9x9或16x16板(: Generates 9x9 or 16x16 board synchronously or asynchronously)

  • 计数(ValCount):抽象类,为一个区域类型(线,正方形或列)的每个可能值实现一个计数器(: Abstract class implementing a counter for each possible value for a type of region (lines, squares or columns))

  • ValCount9(ValCount9):9x9板的ValCount实现(: ValCount implementation for a 9x9 board)

  • ValCount16(ValCount16):16x16电路板的ValCount实现(: ValCount implementation for a 16x16 board) WPF和用户界面类(WPF and User Interface Classes)

  • 应用程式(app):应用(: Application)

  • 关于(dlgAbout):关于盒子(: About box)

  • dlgBoardAppearance(dlgBoardAppearance):对话框更改用于绘制界面的字体和颜色(: Dialog box to change the fonts and colors used to draw the interface)

  • dlgGenerateABoard(dlgGenerateABoard):用于处理板生成的对话框(: Dialog box to handle board generation)

  • 南控(SudControl):从UserControl继承并持有数独板(SudBoard)的可视控件(: Visual control inheriting from UserControl and holding a sudoku board (SudBoard))

  • ValPickerControl(ValPickerControl):实现用于选择要播放的值的值选择器.由SudControl使用(: Implements the value picker used to choose what value to play. Used by SudControl)

  • wndMain(wndMain):主窗口(: Main window) 1.数据结构(1. Data Structures) 值存储在单维数组int [] m_arrBoardVal中.使用一维数组而不是二维数组可以显着提高性能.阵列中的值范围是0到9(对于9x9板)或0到16(对于16x16板).值0表示一个空单元格.数组的第一个值用于存储左上角的单元格值,而最后一个值用于存储右下角的值.(The values are stored in the single dimension array int[] m_arrBoardVal. The use of a single dimension array instead of a two dimension array improves significantly the performance. The values in the array range from 0 to 9 (for 9x9 board) or 0 to 16 (for 16x16 board). Value 0 denotes an empty cell. The first value of the array is used to store the upper left cell value while the last one is used to store the bottom right value.) 存储在单维数组ValueTypeE [] m_arrBoardValType中的值的范围:(The range of values stored in the single dimension array ValueTypeE[] m_arrBoardValType:)

    无(0)(None (0)) 空单元格(Empty cell)
    修复(1)(Fix (1)) 固定值.用户无法更改(Fixed value. User cannot change it)
    用户(2)(User (2)) 价值用户可以更改(Value user can change)

ValueCount类旨在保留线,列和正方形的值计数.每次更新单元格值时,单元格所在的行,列和正方形的ValCount都会相应地更新.(The ValueCount class is designed to keep the count of values for lines, columns and squares. Each time a cell value is updated, the ValCount of the line, the column and the square where the cell is located are updated accordingly.)

m_LineValCount(m_LineValCount) 保持每一行的每个可能值的计数(Keeps the count of each possible value for each line)
m_ColValCount 保持每一列的每个可能值的计数(Keeps the count of each possible value for each column)
m_SqrValCount 保留每个平方的每个可能值的计数(Keeps the count of each possible value for each square)

该程序需要将线性位置转换为直线/列和正方形位置.这些转换使用率很高,必须进行优化(尤其是使用16x16电路板).在16x16电路板上的转换是通过乘法和16乘模完成的.这些操作是使用位移和'＆‘运算符完成的.这就是为什么存在SudBoard9/16和ValCount9/16类的原因.(The program needs to convert a linear position to a line/column and square position. These conversions are heavily used and must be optimised (especially with 16x16 board). The conversion in a 16x16 board is done with multiplication and modulo by 16. These operations are done using bit shifts and the ‘&’ operator. This is the reason why the classes SudBoard9/16 and ValCount9/16 exist.) 使用以下两个数组可以完成从正方形位置到线性位置的转换:(The conversion from square position to linear position is done using these two arrays:)

m_arrPosToSqr(m_arrPosToSqr) 线性位置->正方形位置(Linear position -> Square position)
m_arrSqrToPos 正方形位置->正方形的第一个线性位置(Square position -> First linear position of the square)

数独板类支持撤消或重做动作.为此,两个堆栈保存可以撤消或重做的移动:(The sudoku board class supports the undo or redo moves. To do so, two stacks hold the moves which can be undone or redone:)

Stack m_stackUndoMoves(Stack m_stackUndoMoves)
Stack m_stackRedoMoves(Stack m_stackRedoMoves)

2.动作(2. Moves) 如果输入的值在其列,行和正方形中是唯一的,则定义该移动有效.(A move is defined has being valid if the value being entered is unique in its column, its line and its square.) 更改单元格值的主要方法是PlayAt.该方法更新m_arrBoardVal和m_arrBoardValType数组.它将更新相应的正方形,直线和列ValCount实例.如果指定,则撤消和重做堆栈将更新.(The main method to change the value of a cell is PlayAt. The method updates the m_arrBoardVal and m_arrBoardValType arrays. It updates the corresponding square, line and column ValCount instances. If specified, the undo and redo stacks are updated.) 3.解决木板(3. Solving a board) 给定的数独板不能有一个解决方案,一个解决方案或一个以上解决方案.一种解决方法必须能够找到电路板解决方案(如果存在)并指出是否可能有多个解决方案.(A given sudoku board can have no solution, one solution or more than one solution. A solving method must be able to find a board solution if it exists and to indicate if more than one solution is possible.) 一个简单的回溯方法就足以解决9x9的电路板.(A simple backtracking method can be enough to solve a 9x9 board.)

while No Solution Found
    Find the first empty cell
    For each possible value in this cell
        Play it
        Call recursively
        If Solved
            Solution Found, exit
        Else
            Undo the move
        EndIf
    Next
    Oops, bad board!
wend

但是,使用这种简单的方法来求解16x16电路板太慢了(至少要生成必须多次调用Solve方法的16x16电路板).更好的方法是使用改进的回溯方法:(However, using this simple approach for solving a 16x16 board is too slow (at least to generate a 16x16 board where the Solve method has to be called many times). A better approach is to use an improved backtracking method:)

do {
    Fill the obvious cells
    If solution not found,
        Find the first empty cell
        For each possible value in this cell
            Play it
            Call recursively
            If solve
                Solution Found, exit
            Else
                Undo the move
            EndIf
        Next
        Oops, bad board!
    EndIf
} while No solution found

进一步提高性能的一种方法是预先计算可能的动作列表.现在的问题是实施"填充明显的单元".在这种情况下,显而易见的意思是:(A way to improve further the performance is to compute the list of possible moves in advance. The problem is now to implement the “Fill the obvious cells”. In this context, obvious means:)

  • 只能在正方形,直线或一列的一个单元格中播放的值.(A value which can be played in only one cell of a square, a line or a column.)
  • 只能播放一个值的单元格.(A cell in which only one value can be played.)
    FillListOfValidValuesForEmptyCells(FillListOfValidValuesForEmptyCells) 用可能的动作列表填充数组(Fills an array with the list of possible moves)
    FillValueWhichCanBePlayedInSingleCellOfAZone 填充所有只能在一行,一列或一个正方形中播放值的单元格.(Fills all cells where a value can be played in only one line, one column or one square.)
    FillObviousCells 填充所有明显的值(Fills all obvious values)
    SolveBacktrack 改进的回溯方法(Improved backtracking method)
    Solve 解决董事会(Solves the board)

4.生成数独板(4. Generating a sudoku board) 此板生成器的不同目标是:(The different objectives of this board generator are:)

  • 生成一个只有一个解决方案的有效电路板.(To generate a valid board which has one and only one solution.)

  • 生成9x9或16x16电路板.(To generate a 9x9 or 16x16 board.)

  • 生成不同级别的木板(简单,中等和困难).(To generate different levels of boards (easy, medium and difficult).) 计算机使用三种策略来解决一块木板:(The computer uses three strategies to solve a board:)

  • 用只能在正方形,直线或一列的一个单元格中播放的值填充单元格.(Fill cells with a value which can be played in only one cell of a square, a line or a column.)

  • 填充只能播放一个值的单元格.(Fill cells where only one value can be played.)

  • 蛮力(一一尝试排列)(Brute force (try permutations one by one)) 对于人类而言,第一种方法最简单,第二种更困难,第三种最困难.简易板仅需要解决第一种方法.中型板需要前两种方法,而困难的板则需要解决三种方法.(For humans, the first method is the easiest, the second one is more difficult and the third is the most difficult. An easy board needs only the first method to be solved. A medium board needs the first two methods while a difficult board needs the three methods to be solved.) 该程序用于生成电路板的一般方法是:(The general approach used by this program to generate a board is:)

  • 生成完整的板(To generate a completed board)

  • 只要一一删除值:(To remove values one by one as long as:)

  • 董事会只有一种解决方案(There is only one solution to the board)

  • 仅使用与难度级别兼容的策略(Only strategies compatible with the difficulty level are being used) 开发板的生成由SudBoardGenerator类完成.该板可以在主线程或工作线程上生成.(The board generation is done by the SudBoardGenerator class. The board can be generated on the main thread or on a worker thread.) 4.1生成完整的电路板(4.1 Generating a completed board) 可以使用简单的回溯方法来填充板:(A board can be filled using a simple backtracking method:)

Fill(iPos)
    If Board Filled,
        Return
    ForEach Value
        If Value is valid at this position
            Play it
            If Fill(iPos+1) = Filled
                Return
            Else
                Undo the move
            EndIf
        EndIf
    Next
    <Must never get here>

这种方法将始终提供相同的电路板.为了随机生成棋盘,我们只需要调整填充位置的顺序即可.(This method will always give the same board. To make a random board generation, we just shuffle the order of the filled position.) 通常,使用这种方法生成完整的电路板非常快.但是,某些16x16板有时会花费很长时间才能完成.发生这种情况时,取消生成并重新启动它会更快.(In general, generating a completed board using this method is quite fast. However, from time to time, some 16x16 boards can take a long time to complete. When it happens, it’s faster to cancel this generation and restart it.) 4.2刨花板(开孔)(4.2 Shaving the board (Digging holes)) 生成完整的木板后,我们只需从随机单元格中删除值即可:(Once a completed board has been generated, we just have to remove values from random cells:)

ForEach Pos in Random Order
    Set the position value to 0
    If Solve doesn't give 1 solution or used strategies not compatible with the expected difficulty level
        Restore the value
    EndIf
Next

在16x16板上,此例程可能花费相对较长的时间.因此,可以提供超时.如果达到超时,则该板将仍然有效,但将包含更多已完成的单元格.(On a 16x16 board, this routine can take a relatively long time. For this reason, a timeout can be provided. If the timeout is reached, the board will still be valid but will contain more completed cells.) 5数独控制(5 Sudoku Control) SudControl实现了从System.Windows.Controls.UserControl继承的可视控件.用来玩数独游戏.(The SudControl implements a visual control inheriting from System.Windows.Controls.UserControl. It’s used to play sudoku.)

许可

本文以及所有相关的源代码和文件均已获得The Code Project Open License (CPOL)的许可。

C#4.0 C# .NET .NET4 .NET2.0 WPF VS2010 Visual-Studio Dev Architect 新闻 翻译