[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
KenKen is a Soduku-like puzzle with a little math thrown in. The problem here is to create a playable test-bed program to investigate solver algorithms in the future. At the puzzle owner's request I am informing you that KenKen® is a registered trademark of Nextoy, LLC and that this site is not affiliated with Nextoy, LLC or KenKen Puzzle LLC.
Background & Techniques
The puzzles are played on an N x N board where the digits from 1 to N are placed on the board according to the following rules:
Do not repeat a number in any row or column.
The numbers in each heavily outlined set of squares, called cages, must combine (in any order) to produce the target number in the top corner of the cage using the mathematical operation indicated.
Cages with just one box should be filled in with the target number in the top corner.
A number can be repeated within a cage as long as it is not in the same row or column.
The game was invented in 2004 by a Japanese math teacher for use in his classroom. It is currently licensed by NY Times and other publications. The main site KenKen.com has online playable versions. At the puzzle owner's request I am informing you that KenKen® is a registered trademark of Nextoy, LLC and that this site is not affiliated with Nextoy, LLC or KenKen Puzzle LLC.
I decided to write a simple version to investigate algorithms for writing a solver for the games. Version 1, posted today (Nov. 2009) has the "playable" part, but not the solver part (yet!).
Two puzzle files are included with the downloads. They are straightforward texts file and contain formatting instructions so additional case files may be generated by the user if desired.
Non-programmers are welcome to read on, but may want to jump to bottom of this page to download the executable program now.
One of the early problems to address when designing a program is how to model the data. In this case have these irregular "cages" with a variable number of cells arranged in an irregular pattern. I chose an array of TCagerecs with each cage record holding the Target value, the operation code, and an array of TCellRec records, one for each cell in the cage. Each cell record has the column and row of its position in the grid, the value that the user has assign to the cell, and a 4 character Border array indicating which sides of this cell are exterior walls and need to be drawn with bold lines. Procedure MakeCageOutline checks for cells in the cage which share an edge with another cell in the cage and stops edge drawing for the shared borders.
The cells of the grid contain an encoded string version of the information that is contained in the CageRecs array. If I were to do it over I would probably just encode the indices of the cage record and the cell record but, as it is, exh contains a string of for vbbbbpn..n, where
v is the value entered by the user, bbbb is the border flags field with a "1" indicating to draw that edge counting clockwise starting with the top edge; p is the operation code character, and n...n is the variable length target value field.
Lots of fiddling here with grid drawing . The OnDrawCell event exit has the job of redrawing the border which outlines the cell, the target value, the highlight color for the currently selected cell, the target value and operation in the top left corner of the top left cell, and the value entered by the user as he selects cells and enters values. All fields except the selected highlighted are contained in the cell contents string as described above. The "selected" state is indicated by a flag passed as a parameter by the OnDrawCell exit.
The CheckBtnClick method attempts to detect all errors that might have gone undetected in the case definition or by the user filled values which may introduce duplication errors (same value twice in a row or column) or calculation errors (number in a cell cannot be combined with the given operator to form the target value). be called anytime by clicking the "Check" button. Once all cells are filled, it is called for every change.
Addendum November 15, 2009: KenKen Version 2, posted today, adds the "Solve it" button to let the program solve the currently loaded puzzle. It turned out to be one of those rare occasions where my first approach actually worked and required only a day or so to implement. The technique used was to find all number permutations which satisfy the operator/target value for each cage. These potential solutions are kept in a new Candidates array within the CCells TCellrec records array within each Cagerecs TCagerec record. We then perform a depth-first search applying and testing each cage solution looking for a candidate that does not duplicate numbers in any of the affected rows and columns. If no candidate for a cage is found, one of the previously applied cage solutions must be in error, so we "Backtrack", removing and trying untried candidates, then moving forward again until all cell have been filled and no error remain. All of this happens in the recursive function CheckNext. I also added a third sample case Hard9x9.txt to see if the program could solve it. It does in a second or two.
October 19, 2014: While solving a new KenKen puzzle the other day, I found a couple of irritating program "features" when the user has filled all cells but errors exist. First, automatic checking to produce error messages for every change until the errors were corrected was awkward and just a bad idea. Second, when I tried to fool the program by entering spaces in all of the error locations, I found that space character was not honored as a valid key, Both of those mistakes are corrected today with the posting of version 2,1.
Suggestions for Further Explorations
Copyright © 2000-2016, Gary Darby All rights reserved.