Sudoku solver 10g

Here is a 10g update of last year's 9i Sudoku solver. The row/column/square free values intersection code is simplified by the new MULTISET INTERSECT operator, the validation procedure now uses IS A SET, and I've used MEMBER OF in the new "cross hatching" algorithm. I also used some conditional compilation for diagnostic output.

My original idea was to find the intersection of the three sets of free values for each cell - that is, the available values for the row, the column and the box. I thought this was pretty neat until I looked up Sudoku-solving and found that it was called "Candidate Elimination" (or "Forced Move") and regarded as the most basic approach used by beginners on simple puzzles.

I built on this by adding a guessing loop, in which if the elimination approach cannot complete the puzzle, it takes each candidate value for each empty cell in turn, plugs that value in and retries the eliminator process. It turns out this is another standard technique, known variously as "What If", "Guess-and-Check", "Bifurcation", "Backtracking" or "Ariadne's thread".

Version adds a second deduction approach, in which a possible value for a cell is checked to see if there is anywhere else it could go in its row. If not, then it must go in that cell. This seems to be known as "Cross hatching" within the Sudoku community.

Updated: version 4 now checks the current column and square, and can also eliminate values using a "what if" test, along with some internal refactoring I won't bore you with.

The next straightforward algorithm I want to add in a future version is "matched groups", described in Wikipedia as follows:

One method works by identifying "matched cell groups". For instance, if precisely two cells within a scope (a particular row, column, or region) contain the same two candidate numerals (p,q), or if precisely three cells within a scope contain the same three candidate numerals (p,q,r), these cells are said to be matched. The placement of those candidate numerals anywhere else within that same scope would make a solution impossible; therefore, those candidate numerals can be deleted from all other cells in the scope.

I also want to add what the Brainbashers page calls Intersection Removal, in which for example you narrow down the location of the 5 within a box to one of two positions, and these fall within the same row or column: now even though you don't know exactly which position it goes in, you still have enough information to exclude the rest of that row or column.

Now possibly by this point the code will be sufficiently complex that it would be simpler just to focus on a brute-force "check every possible combination" approach, but that seems to me to defeat the purpose - I wanted a solution using logical deduction.

I should mention that the names in use for sudoku solving techniques seem to vary widely, and I originally made up some of my own before reading up on the subject. The excellent Brainbashers Sudoku Help site, for example, uses "Intersections" and "Pinned Squares" for what I call Locations (there is only one place for the 7 to go), "Forced Moves" for what I call Intersection (the only candidate value for the cell is 2), and "Locked Sets" for what Wikipedia (see above) calls "Matched Groups" (actually I quite like this term and might use it myself). I also realise that I've used the word "square" where others have used "region" or "box".

To install using SQL*Plus, either download sudoku-mk4.pls and run it from the SQL> prompt, or (if you trust me!) paste the following command directly into SQL*Plus:

@http://www.williamrobertson.net/code/sudoku_mk4.pls

To reinstall over an existing version, add the argument "rebuild":

@http://www.williamrobertson.net/code/sudoku_mk4.pls rebuild

This will cleanly drop all sudoku_* types, avoiding type dependency issues.