Representation matrices for puzzle analysis

Tempbow

I was playing around with a program to show a puzzle during its resolution process. Normally I display the 9x9 matrix with the list of possibles in each cell. The aim, of course, is to reduce this matrix via logic rules so it contains just the 81 elements of a resolved puzzle. A possibles matrix may look like this:

rubylips · Posted: Mon Apr 18, 2005 2:00 pm Post subject:

I agree with your basic claim that it's critical to store several state grids if we are to achieve maximum performance. My Java solver solves all 3x3 puzzles - even those that require guesses - in a fraction of a second. Much of its speed stems from its use of three different state grids:

Cell State - boolean[Row][Column][Value] - which stores whether Value is a candidate for the cell (Row,Column).

It's worthwhile to maintain a related matrix int[Row][Column] which stores the number of Values for which the Cell State is true.

Number State - boolean[Value][Sector][Element] - where Sector is a row, column or box, so there are 3*(# Cells In Row) possibilities, and Element is the offset within the Sector of the given cell. Effectively, we characterize a given cell according to Sector and Element rather than Row and Column (of course, there will be three (Sector, Element) descriptions for each cell), but we will achieve dramatic performance improvements in places.

It's worthwhile to maintain a related matrix int[Value][Sector] which stores the number of Values for which the Number State is true.

Information State (actually my source calls it Invulnerable State but Information State would have been a far better name) - int[Value][Row][Column] which is difficult to describe - I'll add a topic at some point - but is critically important in order to compose problems and to guess.

Of course, since we have three state grids, it will take us longer to update state when an elimination is made but it's clearly time well spent.