- - - - - - -
- - - - - - - - - - - -
Other material for programmers
Delphi: Using the computer to solve Sodoku puzzles, with some information about using arrays arising along the way
Introduction: Why this material was put onto the web
I don't think you really want to use the application presented in this tutorial to solve Sudokus. The problem of "How could a computer solve a Sudoku?" tempted me, though, so I wrote the program. You might find the way I used an array instructive. That's why I am publishing this.
I don't propose to go into details of what Sudokus are here. Wikipedia has a good article, if you want it.
Solving a Sudoku entails filling digits from the set 1..9 into squares. (Zero is not used). Sudokus can be solved by a process of elimination. Look for what can't be in a given cell, and, eventually, you will find cells where 8 of the 9 possibilities have been eliminated. When you filed in the remaining digit as the answer in that cell, what is not possible in other cells is extended. Re-assess the grid, fill in newly discovered digits. Repeat until done.
For more on the theory and practice of Sudoku, see Sabu M H's interesting page. If you download the .zip file and don't read the readme.txt, you may wonder where the .exe file is. I >is there... but it was renamed sudoku.bin before being included in the .zip. Just change then name back to sudoku.exe to use it. It worked well, and has a useful option: If you wish, it will flag entries which just can't be right, based on what you know and have guessed so far. It doesn't show you things that are wrong, but, from what you have so far could be right. In other words, it protects you from silly mistakes, but won't "give away" the answer. It will also complete the grid of csndidate digits for you, if you find that part of the solving process a bit tedious. (There is no way... yet... that I could find... to note candidates "by hand". There are puzzles which cannot be solved using just the qutomatic candidate finder. Sometimes there are no cells with only a single candidate.) (To start a new puzzle, either use the button for that, or the "New Puzzle" option under the "Puzzle" menu item. This is only logical, after all, but maybe you, like me, are used to looking for "New..." under the "File" item? Which is about as logical as clicking the "Start" button to stop Windows. The things we can be trained to find "normal". Sigh.)
What is on the web
A zip file awaits your downloading pleasure. It contains the sourcecode for most of my Sudoku application.
a) Apologies: I mis-spelt "Sudoku" while working on the project.
b) You will need a Delphi compiler. I have not included a copy of the exe. I did this work with Delphi 2.
c) A critical piece of the heart of the program is incomplete! This is to give you a programming challenge. Have fun. (More is explained below.)
The application, as supplied, will "run" (once compiled), but it will get the answer wrong. It will fill in things where they don't belong, because it will come to wrong conclusions about what can't go in certain places. However, most, if not all, of what you have to re-program is within the UpdateCellInfo procedure.
What the finished application does
When you run the application, a Sudoku puzzle appears on the screen.
There's a button marked "Execute one pass...". Click this, and the application looks at the digits already placed on the screen, and, in each empty cell, marks what digits could not go in that cell. It conveys this information with a a grid of 9 dots (3 rows of 3). If there's a dot in the upper left, then the cell cannot hold a 1. If there's a dot in the upper middle position, then the cell cannot hold a 2, and so on.
If any cell could not hold 8 digits, based on the digits already filled in, then the cell is filled in with the remaining, only possible, digit. (Zeros are not included in Sudoku squares.)
Well... that's what the finished application does. The version supplied in the zip has a fatally stupid UpdateCellInfo procedure. More on that later.
Watching the finished program at work is quite amuzing... you see the "can't be that one" dots proliferating with each click of the "Execute one pass...." button.
Structure of the application's code
If I do say so myself, the program is quite well broken down into functional units.
The FormCreate event handler is simply....
FillVarWithDefaults fills sundry variables with values which will always be good initial values.
FillInKnown fills in values which make the application solve the particular puzzle that it does solve. This is the place you'll have to do some work if you want to extend the application so that it can solve other Sudokus. When you've read the material below about the arrays used in the application, I think you'll understand what is needed.
PrepareDrawingArea is called just once. It sets up an area for plotting "graphics" on. Some text (the filled in digits) is also "plotted" on the canvas, using Delphi's TextOut method.
DisplayTable fills the display with what is known at any given time, digits for known digits, and patterns of dots for digits which cannot appear in a particular cell. It could be improved- the dots remain and make the display a little messy even after the digit for a cell has been deduced. DisplayTable, unlike the other procedures called by FormCreate, is called again, many times, later in the application's execution.
Array used in the application
The "secret" of this application is the array bCellInfo. It is a three dimensional array. Each element holds a byte. Each element of the array will only ever hold a number in the range 0-9, inclusive.
The first two indexes (is that the right term?) tell you which cell in the Sudoku puzzle you are dealing with. e.g., the upper left hand cell's bCellInfo data is held in....
If we have not solved what digit should appear in this cell of the puzzle, then bInfo[0,0,0] will hold 0. Once we have solved the cell, bInfo[0,0,0] holds the number which should appear in the cell. If you look at what is happening during the FillInKnown procedure, you should be reassured that you have understood what I've said so far.
Likewise, if we know that the cell in the bottom left of the puzzle should be filled in with a 5, we will find that bCellInfo[8,8,0] is holding a 5. If the cell in the lower left of the puzzle should be a 9, then bCellInfo[0,8,0] holds a 9.
The other array elements assigned to each cell of the puzzle will all start with 0's in them. Whenever the application determines that a particular cell can't hold a particular digit, one array element is change to hold a 1. E.g.: Suppose we don't yet know what should be in the upper left hand corner of the puzzle, but we deduce that it can't be a 7. We would set bCellInfo[0,0,7] to 1 to record that information.
Now that you know a little bit more about the application and its data structure, I can say more about UpDateCellInfo.
The UpDateCellInfo procedure merely calls three sub-routines: UpdateCellInfoHoriz, UpdateCellInfoVert, and UpdateCellInfoLocal8.
The routines look to see what digits are not possible in a particular cell, based on what digits have already been filled in elsewhere. Each routine is called with two parameters. They tell the routine which cell we are working with. E.g., if we are checking what digits are impossible in the center cell of the top row, we call UpdateCellInfo(4,0). Each makes changes to what's in bCellInfo[x,y,d] as appropriate. Other parts of the program, already finished and working, I believe, act on the information.
UpdateCellInfoHoriz looks to see what cells to left and right of the current cell can tell us.
UpdateCellInfoVert looks to see what cells above and below the current cell can tell us.
UpdateCellInfoLocal8 looks to see what cells in the current cell's ninth of the whole puzzle can tell us.
If you've struggled with the programming, and are frustrated and desperate, feel free to email me, and I can send you "the answer"... but please keep it to yourself, to preserve the next person's "fun"?
I found the exercise quite fun. I think it would make an excellent challenge for anyone running a programming competition.
Prizes could be offered for various categories:
--Smallest program. (Please stipulate that all variable names must be 8 characters long, to ensure participants use meaningful names!)
--Fastest program. (Time to solve 5 previously unseen Sudokus to determine winner.
--Program successful with fewest variables. (Be careful that no "cheating" is possible, e.g. using the caption of a label to hold data.)
If setting up a competition, an organiser would be wise to stipulate a common data structure for the datafile defining each puzzle, and a standard mechanism for timing how fast the application solves a given puzzle.
Click here if you're feeling kind! (Promotes my site via "Top100Borland")
Ad from page's editor: Yes.. I do enjoy
compiling these things for you... hope they are helpful. However..
this doesn't pay my bills!!! If you find this stuff useful, (and you
run an MS-DOS or Windows PC) please visit my freeware and shareware
page, download something, and circulate it for me? Links on your page
to this page would also be appreciated!
Click here to visit editor's freeware, shareware page.
Link to Tutorials main page
How to email or write this page's editor, Tom Boyd
Page WILL BE tested for compliance with INDUSTRY (not MS-only) standards, using the free, publicly accessible validator at validator.w3.org
If this page causes a script to run, why? Because of things like Google panels, and the code for the search button. Why do I mention scripts? Be sure you know all you need to about spyware.
....... P a g e . . . E n d s .....