Programming languages for implementing solvers

i_smith

As a newcomer to Sudoku with some computer programming background, I decided to write a solver to help me with my obvious shortcomings as a pencil-and-paper solver. I implemented my solver in a programming language called Nial, (available as a free download) which is a descendant of IBM’s APL IBM’s APL2 and Jsoftware’s J are other descendants. These languages have many powerful array and set operations that allow solver operations to be expressed very compactly (the file containing my solver and all of its support routines is 441 lines long, including the blank lines between function definitions). The key language feature is that an element of an array can itself be an array, which among other things makes it very easy to create and manipulate arrays of candidate lists. I didn’t set out to write a solver that would do anything more than solve the daily Sudoku published in the Boston Globe, and I’m not even sure why mine works on the more difficult Sudokus published elsewhere. It has solved, for example,

• all 30 of the very hard Sudokus published on the Logic website

• all of the benchmark Sudokus on the Sudoku Players Forum except the three designated as “extremely difficult”

• all of the “devilish” Sudokus in Tetsuya Nishio’s books, Higher Sudoku (Vertical, 2006) and Extreme Sudoku (Vertical, 2008)

• All of the “super-fiendish” puzzles in Wayne Gould’s book, Fiendish Su Doku (HarperCollins, 2006)

My solver cannot solve Sudokus on the level of the Top1465. These seem to be specifically designed to frustrate any attempt to find and exploit patterns, weaknesses, and trapdoors.

Here’s a rough outline of my solution method:
Step 1 (logic)
Repeatedly apply the three basic methods—scanning, singles, and elimination—until no additional cells are solved. Whenever the candidate-finding routine is called, it attempts to reduce the number of candidates via naked pairs. If the solution is found, STOP; otherwise continue to Step 2.
Step 2 (generate and filter)
First, attempt to reduce the number of candidates via line-box interactions. Then, find all the unsolved cells in the updated puzzle grid that have the smallest number, n, of candidates (usually n = 2). For each such cell, construct n trial grids and place one of the candidate values in the appropriate cell of each grid. Apply the Step 1 procedure to each trial grid and discard any invalid grids (i.e., grids that violate the fundamental rule of Sudoku). Find the candidates in the remaining grids and discard those which have no candidates in one or more cells. If one or more trial grids have exactly one candidate per cell in all 81 cells, select the first such grid. That is the solution: STOP. Otherwise, sort the trial grids in decreasing order of number of solved cells. Apply Step 1 and Step 2 to each trial grid in turn until a solution is found or until the last trial grid has been processed. In practice, the solver has to re-apply Steps 1 and 2 in this fashion only occasionally.
Limitations of the solver
With puzzles of the Top1465 variety, my solver reaches the end of Step 2 with a set of partial solutions and then gives up. Re-applying Step 2 by hand usually ends up in a blind alley. By following an initially promising sequence of partial solutions containing ever more solved cells, you eventually reach a dead end when the candidate-finder produces a grid with one or more cells having no candidates.

Adak · Posted: Thu Apr 02, 2009 4:36 am Post subject:

You see that you need backtracking. If a cell has only 3 possible candidates for it's final value, and the first number you try leads to no solution, you need to restore the grid to it's former value (just before you tried your first candidate number), and then try candidate #2. Then repeat for #3, if necessary.

You're also doing some extra work I believe. All you need is an index of cells, (or it's equivalent in Nial, and then sort the index so the cells with fewer candidates are at the top of the indexed list.

Sounds like your program is making up possible grids before they're needed. In many cases, I believe you'll find that all those grids are never needed.

You want to make up your grids in JIT mode.