Subset algorithm with bitwise math

Lummox JR

I wrote this algorithm to solve for subsets via bitwise arithmetic. I hope people will find it useful.

SarC · Posted: Wed Oct 26, 2005 11:00 am Post subject:

I want, like most other here, program my own logic sudoku-solver. And after twisting my brain trying to find a good algorithm to find naked and hidden pairs/triples etc, I found this post.

But my problem is that I've never programmed in C++ so I can't really read the source. I've read through your explanation a couple of times, but I can't really figure it out.

So if anyone could translate it to Delphi/Pascal that would be amazing, but that's asking too much heh. But Lummox JR, if you could show me an example of how your routine works, I might be able to figure out the logics, and program my own copy in Delphi. Cool

Lummox JR · Posted: Wed Oct 26, 2005 8:52 pm Post subject:

Well, it is kind of a complicated algorithm, so no surprise that it was hard to figure out.

The most important thing to start with is that you must have an array of size*2, i.e. 18 for standard sudoku. The first half should be loaded with bit flags for one orientation, and the second half should have them transposed. For naked subsets, each "column" (element in the array) is a position within a box/column/row; each "row" (bit) is a digit. Hidden subsets do this the opposite way. This algorithm relies on both being present, so it can bail out of one test and try another to save time. If you have only 7 choices to loop through, the most you'll find is a triple, so if a naked pair or triple can't be found, it will try finding hidden pairs or triples.

Now the simple parts. Clear out the result array, which is also size 18, for use later. For each half of the flags array, do the following:

1) Count the number of choices, C. Any array element or bit set to 0 represents a constraint that was already filled, so we don't worry about it. The number of choices is the number of non-zero values in this half of the flags array. As you count the choices, also put them into the stack array and also find the "highest" choice, mi. If C<4, we can't possibly find any subset as large as a pair, so bail out.

2) The stack array works as follows: It holds the current subset at the beginning, the other choices at the end. You also keep track of the current subset size, c, and the last value you added or tried to add to the subset, k. The subset is stored in ascending order. There is also a bits stack array, bits, which we will fill later. The bit values of the current subset are stored in b. Start with k=-1 (or size-1 for the 2nd half of the flags array), c=0, and b=0.

3) Set j=C. If we are not past the limit (limit=2 is a pair), and if (c+1)<=C (i.e., we're not looking for too big a subset), and if k<mi (there are still more choices for the subset in ascending order), find the next possible value stack[j] to add to the subset. Do this by looping through i from c to C-1, and if j>=C (no j chosen yet) or stack[i]<stack[j] (smaller value found), set j=i.

4) If j>=C, that is if nothing was found, pop k from the stack. If there's nothing to pop, move on to the next half of the flags array or else exit the function with return value 0 (no subsets found). Otherwise, decrement c, and then pull b=bits[c] off the stack.

5) Swap stack[j] and stack[c] so the first part of stack, the part that holds the subset we're looking at, is in ascending order. Set k=stack[c], push k to the stack, and push b to the bits stack. Now add the bits of flags[k] to b via OR, and find nb (number of bits) with countbits(). I'll explain that function later.

6) If nb<=c, we have a subset size c with nb values; they should be equal if so; the <= test is just for safety. If nb>c instead, go to step 7. If we have a subset, we want to eliminate the bits in b from all other parts of this half of the array that are not in the set. Now, search all remaining values in the stack array that are not part of the current subset (indexes c through C-1). If for any i from c to C-1, you find that flags[stack[i]] AND b is nonzero, set result[stack[i]]=flags[stack[i]] AND b, and also note that we will be returning a positive value. If a result was not found, set k=mi to stop looking for additonal columns for this subset; it's not one that interests us. If a result was found:

6a) If we are in the first half of the flags array, set ret=1 (the return value), and *x=ints2bits(stack,c) and *y=b. ints2bits fills in bit flags with the columns that were part of the subset, stack[0] through stack[c-1]. Go to the cleanup section to deallocate memory and also copy the result array into the flags array.

6b) If we are in the second half of the flags array, set ret=2, *y=ints2bits(stack,c), and *x=b. Go to the cleanup section.

7) If nb>=c, then if nb>limit, we have too many values to make a set within our limit. If nb*2>C, then if there is a subset to be found we're better off searching the other half of the flags array. Either way, set k=mi to stop searching within this potential subset; it does not interest us.

Now once this routine returns, if ret==1 it found a subset in the first half of the flags array; otherwise if ret==2 it found a subset in the second half. This tells you the difference between naked and hidden subsets, or X-wings/swordfish by column or row. If you set this up so the first half is for naked subsets, the x value now has the positions for the subset, and y has the digits, both stored in bit flag form. The flags array will have all 0's except in places where you can make eliminations.

The countbits() function looks like this:

SarC · Posted: Wed Oct 26, 2005 11:55 pm Post subject:

Amazing Lummox JR! Thanks alot.
I'm still trying to grasp the idea of having bits represent the values, so if you could tell me if I got this example right:

xyzzy · Posted: Thu Oct 27, 2005 7:55 am Post subject:

Here is a recursive algorithm which I think is much easier to understand.

SarC · Posted: Thu Oct 27, 2005 10:43 am Post subject:

@xyzzy: Thanks alot for helping out. I've translated your function to Delphi and tried it out, but I must be doing something wrong. With the example I posted, the function spits out 'The sets 128 make a subset with union 258', which doesn't seem to be right.
I suspect that its the way I make the bitset, so if you could check this code and see if its correct:
(example is Row: {5} {7} {1} {2,4} {2,4,9} {2,9} {3,4,8} {6} {2,3,8})

xyzzy · Posted: Fri Oct 28, 2005 12:27 am Post subject:

SarC · Posted: Sun Oct 30, 2005 3:22 pm Post subject:

xyzzy · Posted: Tue Nov 01, 2005 9:24 am Post subject:

foundset is the correct value so it must be finding the subset, but just not returning the value correctly.

I've never used Delphi, but I think this line has a bug:
If TmpSet = Search(Start + 1, Size + 1, TmpSet) Then

You want to assign the result of the Search() to TmpSet, and check if it's true. You probably want to use := instead of =. Maybe you're not allowed to use a := as an expression in Delphi like you can in C? I don't think you can in Pascal.

SarC · Posted: Tue Nov 01, 2005 1:42 pm Post subject:

You are absolutely correct! I didn't notice that it wasn't a ==. C++ can be so tricky Wink

Thanks alot for looking through it and helping me out!

xyzzy · Posted: Wed Nov 02, 2005 10:00 am Post subject:

Another optimization you can do, which makes the search a great deal faster, is to make this change:

dukuso · Posted: Wed Nov 02, 2005 10:55 am Post subject:

what about this wellknown bipartite matching algorithm ?
Is it not competitive yet for 9*9 or too complicated ?

xyzzy · Posted: Wed Nov 02, 2005 1:55 pm Post subject:

Bob Hanson · Posted: Thu Nov 03, 2005 6:12 am Post subject:

The recursive method can also be seen at http://www.stolaf.edu/people/hansonr/sudoku/subsets.js

in JavaScript it is simply:

function analyzeX(z,type,iscanfirstindex,List,ipt,jlist,ilist,nx,ny,msg){
var maxdim=List.length/2
if(ipt>=List.length||nx>maxdim||ny>maxdim)return 0

var maxlen=List.length/2+1

//propagate to next row

analyzeX(z,type,iscanfirstindex,List,ipt+1,jlist,ilist,nx,ny,msg)
if(iseliminated)return 1

//OR in these rows and count them

var i=List[ipt] //another row/col
ilist+=Pwr2[i]
if(iscanfirstindex){
jlist=jlist | Possible["X"+type][i][z]
}else{
jlist=jlist | Possible["X"+type][z][i]
}
nx=xNum(jlist)
ny++
if(nx>maxlen)return 0
if(ny==nx && analyzeFoundX(z,type,iscanfirstindex,jlist,ilist,nx,msg))return 1
return analyzeX(z,type,iscanfirstindex,List,ipt+1,jlist,ilist,nx,ny,msg)
}

As mentioned, this just keeps checking all possible combinations until it finds that the number of nodes equals the size of the set (nx=ny). It covers X-wings, swordfish, and n-tuples hidden and naked in blocks, cells, or rows, depending upon the contents of List and the parameters "type" and "iscanfirstindex".

This routine automatically returns the smallest-size hit that results in an elimination due to the double recursion at both the beginning and the end.

Also, as a note, by checking for actual elimination [in analyzeFoundX()]-- not just the presence of the object, it can continue until either exhausting the possibilities or finding something that can advance the solution.

Works like a charm.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

siftings · Posted: Wed Feb 22, 2006 11:56 pm Post subject: Help converting code

I am also trying to create a solver, but in java. I tried converting your code, but the following doesn't find any subsets. I noticed your code uses the function numbits instead of countbits, but they're the same right? Thanks...