sudoku in C

>>If board[i][k] is represented by setting a different bit for each possibility, then you can implement union as the | of all the board values

you mean like 1 || 2 || 3 ... || 9?

but wouldn't that just give 1 in the end?

Hm... | is the bit wise or? Then the maximum value it would give me is 9, right?

Knowing the game, the board is most likely to contain numbers, not bits.

I would suggest you read "singleton" as meaning "does not contain a number".

Also read "UNION" as something like "all numbers seen".

Play the game a few times. Among the rules there is "a row/column cannot contain the same number twice". That looks very much like "isum" and "jsum".

Paul

if not, here is one table :)

This one works only for nibbles [0..F], however it's not difficult to create a function that will support a byte or a bigger int number.

here an example:

static const char bitCountTable[16] =
{
   0,
   1,
   1,
   2,
   1,
   2,
   2,
   3,
   1,
   2,
   2,
   3,
   2,
   3,
   3,
   4
};
 
char bitCount(char data)
{
   char result;
 
   result = bitCountTable[((data & 0xF0) >> 4)] + bitCountTable[data & 0x0F];
 
   return (result);
}

                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:

Thanks for the help so far =)

I need a bit more help with debugging this for "harder" sudoku boards, where we don't have as many numbers to help...

This code works for boards with a nice bunch of numbers, but it leaves a few squares unsolved when you don't give it enough numbers.

//GRID_SQUARED = 3 * 3;
//ALL_VALUES = (1<<GRID_SQUARED)-1
 
bool rule2() {
  bool changed = false;
  int isum=0, jsum=0, ksum=0;
  for (int i = 0 ; i < GRID_SQUARED ; ++ i) {  
    for (int j = 0 ; j < GRID_SQUARED ; ++ j) {
      //for every square, if the value is not a singleton, 
      int value = board[i][j];
      if (!singleton(value)) {
		
	//union of all values of same column different rows
	for (int k = 0 ; k < GRID_SQUARED ; ++ k) {
	  if (k != i)  
	    isum |= board[k][j];
	}
		  
	if (isum != ALL_VALUES) {
	  board[i][j] = isum ^ ALL_VALUES;
	  changed = true;
	}
		
	//union of all values of same row different cols		
	for (int k = 0 ; k < GRID_SQUARED ; ++ k) {
	  if (k != j) 
	    jsum |= board[i][k];
	}
		  
	if (jsum != ALL_VALUES){
	  board[i][j] = jsum ^ ALL_VALUES;
	  changed = true;
	}
		  
	//union of all values of 3x3 square not including (i,j)
	int ii = i;
	int jj = j;
	for (int k = ii ; k < ii + GRIDSIZE ; ++ k) {
	  for (int l = jj ; l < jj + GRIDSIZE ; ++ l) {
	    if ((k == i) && (l == j)) {
	      continue;
	    }
	    ksum |= board[k][l];
	  }
	}
		  
	if (ksum != ALL_VALUES){
	  board[i][j] = ksum ^ ALL_VALUES;
	  changed = true;
	}			
      }	
    }		
  }
  return changed;
}

                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:

Hm... i tried debugging this myself, I commented out the rows first... and then the columns, and then the square... and each and every time, I got the same result, is that supposed to happen? I understand that they are implementing the same logic, but they are given different number sets, so shouldn't the output be at least a little different?

I'm sorry phoenix... just so I understand what u'r saying here:

>>bitCountTable[((data & 0xF0) >> 4)] + bitCountTable[data & 0x0F];

data wasn't assigned anything right?, so are you anding it with the size of the full sudoku board, and then bit shifting it by the size of the square?

And then adding the value in bitCountTable[data & 0x0F]?

>>bitCountTable[((data & 0xF0) >> 4)] + bitCountTable[data & 0x0F];
This counts up to 8 bits.
If your design stores 9 different values in data as 9 different bits.
then your count may go up to 9

>>The bitCountTable has the number of bits present in one nibble, from 0x00 to 0x0F, the function takes the MSN (Most Significant Nibble) and shift it right by 4 bits which will be the value of the higher nibble and adds the number of bits counted in the lower nibble.

wait... does that mean the number 4 has anything to do with the size of the sudoku board or not? Or is it because a nibble has 4 bits, and by shifting it by 4, you get the MSN?

If the second one is true... I'm not exactly sure how to scale that for the 9x9 sudoku board... I was thinking I could try shifting it 9 bits (because I thought 4 was the number of squares in the smaller square), and do it that way...

Sorry, ozo's comment didn't show up when I posted my reply... so was I right in thinking that I had to shift the bits by 9?

shifting by 9 instead of 4 won't help unless you extend bitCountTable,
and if you extend bitCountTable, then you may not need to shift by 9,
unless data can hold 18 different bit values

Did you say in the original question that you already got the bit_count and  get_nth_set_bit functions figured out?
How did you implement them. and what happens if you use the functions that you got figured out?

I'd have to know more about how the functions that you have posted fit into the overall program to know whether a bitCount that works up to 9 would solve your problem,
but if you extend bitCountTable up to 31
and you changed the & 0xF0
then the bitCount routine might work for 9 bits,
But unless chars on your machine hold more than 8 bits, it wouldn't be a char function.

I''m not sure what that has to do with your problem, since I don't see you calling the bitCount function anywhere.

This is what I've got for the other functions.

nt bit_count(int value) {
 int count = 0; //initialize count variable
 while (value != 0){  //check if n is 0.  If it is 0 then just return 0.
   if (value & 1)   //by ANDing n and 1 we check if the right most bit is 1.
     count++; //if the right most bit is 1 then increment count
   value = value >> 1;  //shifting n to right one bit gives us the
next bit to check.
 }
 return count;    //once we've gone through all of n, 0s would be
shifted in and the loop will end.
}

int get_nth_set_bit(int value, int index) {
 int position = 0, count = 0;
 while (count <= index){
   if (value & 1)
     count++;
   value = value >> 1;
   position++;
 }
 return (position - 1);
}

>I don't think you need to extend bit count table. You could create a int (16 bit) bit count, just need to consider 4 nibbles instead of 2.
my comment was in reference to changing >>4 to >>9
that is not what you did.

>> my comment was in reference to changing >>4 to >>9
Why would you change the shift from 4 to 9?... the function objective is to count the number of bits in a given data. Changing the shift from 4 to 9 will give you a bad result.

>> that is not what you did.
what I have understood here is that a bit count routine is needed. The last one I posted will work up to 16 bits.

>> but if you extend bitCountTable up to 31
and you changed the & 0xF0
then the bitCount routine might work for 9 bits,
But unless chars on your machine hold more than 8 bits, it wouldn't be a char function.

Normally char will be 8 bit long (this may change of course)... The last routine supports 16, and you need to count up to 9 bits... so it will work.

>> Changing the shift from 4 to 9 will give you a bad result.
As I said.

>> But unless chars on your machine hold more than 8 bits, it wouldn't be a char function.
again, we agree

huh...

I see that this interesting problem is not closed. Do you still have a question ?
I'm afraid you have used thin both phoenix and ozo with the bit_count issue which was not the worst problem you had.

You should give them credit for their work, close this one and open a brand new topic with where you are in this task, to help us understanding your current problem
I have more than once told myself I should try tackle this sudoku solving algorithm (but C would not be my favorite choice there. Delphi might be a lot easier)

For the bit count , I assert you that phoenix solution is the right one. If you don't see why, don't bother with low-level functions and concentrate on higher ones, and trust experts. I have just added a loop, it's more elegant and can be scaled for wider use (32 bits) on other applications.

char bitCount(int data)
{
   char result=0;
 
   while(data)
   {
      result += bitCountTable[data & 0xF];
      data >>= 4;
   }
   return result;
}

                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11: