6.21 Sudoku checker

#1

Hi,

I was wondering why the solution to this problem seems so complicated. Why not just check all elements in one pass, since we have 9 rows, 9 columns and 9 3x3 grids, we need 27 bits per digit (1-9), which would be sufficed to keep in array of 9 integers. Then as we iterate through the board we check 3 flags for given digit (1 for row, 1 for column and 1 for 3x3 grid) and if any set then the board is invalid. Otherwise we set these 3 flags for a given digit. This could be generalized to nxn board if necessary, just need more storage for the array of bit flags.

Thanks,
Yev

0 Likes
#2

Hi @yevvi,

Many thanks for your question, and would you mind to show here your code? Also, what language you are using because I think current solution is also checking those constraints like you said.

0 Likes
#3

Sure, here is the code in Java, this is for 9x9 board only though:

	public static boolean sudokuCheck(int [][] b)
	{
		assert(b != null && b.length == 9);
		assert(b[0] != null && b[0].length == 9);
		
		int [] f = new int[9]; //bits 0-8 rows, 9-17 columns, 18-26 3x3 sub-arrays
		
		for(int i = 0; i < 9; i++)
			for(int j = 0; j < 9; j++) {
				int d = b[i][j];
				assert(d >= 0 && d <= 9);
				if (d == 0)
					continue;
				int rowMask = 1<<i, colMask = 1<<(9+j), subMask = 1<<(18 + 3*(i/3) + (j/3));
				
				if ((f[d-1] & rowMask) != 0 || (f[d-1] & colMask) != 0 || (f[d-1] & subMask) != 0)
					return false;
				f[d-1] |= rowMask|colMask|subMask;
			}
		return true;
	}
}

Thanks,
Yev

0 Likes
#4

Hey @yevvi,

Thanks for this sharing, and your code reminds me the code gulf I participated before. It is smart to use integer with bitmask as hashtable. However, it is important to have more readable code for everyone. So we decide to make this one with more structure code.

Anyways, it is great to read your code, which reminds me the old times when I participated programming contest and code golf.

0 Likes
#5

Thanks. Yeah, with int array of bitmasks it is easier to go through through the input in one pass. Although it can also be done with 2D boolean array 9x27.

Code golf looks like an interesting contest to participate in addition to solving EOPI problems.

Thanks,
Yev

0 Likes