Pure PL/SQL Sudoku solver

Back when Sudokus were new-ish and everybody was writing Sudoku solvers as a coding challenge, it occurred to me in a moment of inspiration that you could probably deduce most blank cells' values by finding the intersection of the unused values for their row, column and square. So for example, if the cell's row currently contained all the numbers exept 1, 2 and 3, its column all except 2, 3 and 4, and its square all except 3, 7 and 9, then the missing value must be 3. This wouldn't work for every cell of course, but if you kept looping over the puzzle using this method to fill in every blank you could, maybe that would be a set-based way to solve it.

I thought this was pretty neat until I looked up Sudoku-solving and found that my briliant technique was called "Forced Moves" and regarded as the most basic approach used by beginners on simple puzzles.

After some more thought, I came up with 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 "Intersections" and is also regarded as basic.

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". (I'm less keen on this kind of brute-force approach to be honest, as I'd prefer my programming challenge to use proper logical deduction, but used as a final when-all-else-fails method it cracks a lot of ultra-fiendish Sudokus that it otherwise couldn't.)

The row/column/square free values intersection code uses the handy multiset intersect operator, the validation procedure uses is a set, and I've used member of in the "cross hatching" algorithm. I also used some conditional compilation for diagnostic output.

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.

To install using SQL*Plus, download sudoku.pls and run it from the SQL> prompt.

@sudoku.pls

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

[an error occurred while processing this directive]

Source code: