AWK sudoku solver, and some ideas on data representation

Goran

It's fun to see how many programming languages are used to program solvers (even SQL). Let me add awk (using the GNU implementation), my favourite since it's interpreted and thus incredibly quick to correct bugs.

I have programmed a solver that using about five rules with variations of them, and started on the brute-force backtracking fallback (not difficult either). I don't mind the character-oriented user interface of awk, I enter puzzles as text.

On a fast machine, it finds most solutions immediately. My main idea is to use bit patterns for data representation as much as possible in order not to have to check individual digits.

Thus, there is an array <possibles> with one word for each board square and one bit set for each still possible digit in that square. That gives you rule 1 (only one digit possible in a square) immediately: Code statically the nine bit patterns of one 1 and eight 0's, and check for them. In awk, which has associative arrays, this becomes both real code and pseudo-code:

for (i = 0; i <= 80; i++)
if (possible[i] in singletons)
<Square with rule 1 found>

For certain rules, I do the reverse, viz. form an array with one word representing the possible squares of a line for each digit.

If someone feels this is useful or had smarter ideas and cares to discuss this, please do so.

Best,
Goran

hhalkin · Posted: Sun Aug 14, 2005 3:23 pm Post subject:

Hi Goran,

I have been using that binary representation for about two weeks.
I am programming in tcl (an interpreted language with bitshift and
bitwise operations). I also constuct a large number of fixed arrays:
for instance an array mapping each cell index into a triplet indicating
its row, column and block etc.

I have constucted my own set of logic rules and I have
not yet compared my rules with the set of rules like Nishio,
Supercoloring, Jellyfish, Swordfish : it is sometimes more fun to follow
my own ideas than to figure out what other people are doing.

My solver can handle the 100 hardest sudokus posted by dukuso
on August 10 at

http://www.setbb.com/phpbb/viewtopic.php?t=132&mforum=sudoku

What is very strange is that there is no corrolation between my difficulty
index and the hardness-score of dukuso: this means that I would
benefit by studying all those exotic rules!

Hubert

Goran · Posted: Sun Aug 14, 2005 4:44 pm Post subject:

Hi Hubert,

Agreed on

-- fixed arrays being a good thing, also using several. Would be interesting to compare :-) For instance I use an array of the squares lines (a line = a row or col or bux) instead.

-- more fun to figure out your rules yourself. Not familiar with those sets you mention.

Figuring out what bitwise ops to use to accomplish a useful task -- i.e. detecting a rule -- is also fun. AWK actually stores all numbers as a double real, imagine the overhead converting back and forth.

Does your solver do it analytically (manage the 100 hardest)?

Is there an accepted difficulty index?

It would be fun to have one's solver converted into a language with a GUI. AWK is pretty C-ish, so it should not be that hard. Someone ought to do GUI frontend to which you could hook up any solver with some accepted protocol -- essentially the starting position as text input.

Best,

Goran