|
| View previous topic :: View next topic |
| Author |
Message |
| jemore2
| | Joined: 02 Feb 2006 | | Posts: 4 | | : | |
Items |
|
 Posted: Thu Feb 02, 2006 8:07 pm Post subject: How to validate a sudoku grid |
 |
|
Hi there.
After folding a bit in this forum, I did not found a smart way to validate a Sudoku grid. In other terms, I'm looking for a algorithm to check if a grid is a Sudoku, if it is correctly filled.
I'm writing a Sudoku games in DoJo, for i-mode cellphone, and I have a few constraints to implement this algorithm :
- must be in java
- must be quick
- must use a litle memory.
I do not want to use the first technic that come in mind, let's say checking if there is all the number from 1 to 9 in line, row and sector, because it can be huge in memory and slow.
I think there is a smarter way by summing the number in rows and cols, or doing a kind of CRC of the numbers of the grid.
The summing method can be fooled if you invert two numbers in a row or a cell. My simple CRC method can alsbo be easily tricked.
Are you aware of a such technic, that do note use an array to store the numbers in row, colls and sector ?
Thanks
Jerome. |
|
| Back to top |
|
 |
| evert
| | Joined: 30 Aug 2005 | | Posts: 68 | | : | | Location: Amsterdam |
Items |
|
| Posted: Fri Feb 03, 2006 9:35 am Post subject: |
|
|
| What's CRC? |
|
| Back to top |
|
|
| dom
| | Joined: 10 Nov 2005 | | Posts: 42 | | : | |
Items |
|
| Posted: Fri Feb 03, 2006 10:27 am Post subject: |
|
|
Summing the numbers will fail on a grid of all 5's
555 555 555
555 555 555
555 555 555
555 555 555
555 555 555
555 555 555
555 555 555
555 555 555
555 555 555
As all rows, columns and regions now add up to 45...
My recommendation would be to just cycle through each house and count instances of each digit in a 9 value array. If the count for a digit exceeds 1 then the board is invalid.
i.e.
| Code: |
function isValid(house)
{
byte valueFound[] = {0,0,0,0,0,0,0,0,0};
for (i=0; i<9; i++)
{
// increment count for this value
valueFound[house[i]]++;
// if we've found two of them then this house is not valid
if (valueFound[house[i]]>1)
return false;
}
return true;
}
|
If memory is really tight then rather than a 9 value array (9 bytes) you could use an 18 bit mask (3/4 bytes) such that 0x1 is the bit for 1, 0x4 is a bit for 2, etc.. Then add the bitmask to that integer for each digit that is set. If any even bits are set then there is more than 1 of that digit.
i.e.
(in binary)
....000101
would be a digit for 1 and a digit for 2
Then add another digit for 1...
....000101 + ....000001 = ....000110
Then test for even digits using value&....101010 >0
Does that make sense?
Anyway, that's a memory efficient way to look for two of an integer type, it's O(n) where n is number of digits in a house so also pretty efficient. If that doesn't make sense I can probably make it clearer!
_________________
Orangeminds Sudoku
http://www.orangeminds.com/sudoku/ |
|
| Back to top |
|
|
| jemore2
| | Joined: 02 Feb 2006 | | Posts: 4 | | : | |
Items |
|
| Posted: Fri Feb 03, 2006 6:23 pm Post subject: |
|
|
CRC : http://en.wikipedia.org/wiki/Cyclic_redundancy_check 
What I mean by CRC in a completed Sudoku grid, is a way (ie algorithm) to compute a number, which is always the same, whatever the grid is , at the condition that the grid is complete and valid. An unvalid grid will result as a wrong CRC. (To be precise, it is not a real CRC, but I understand myself...)
My first method to compute the CRC was to shift a bitmask by the number present in a cell, by row, and to sum this shifted register until all the line was browse. It result of crc value of 0x3FE000000001L if the grid is complete. But it can be fooled in some case, if you invert two values.
I'm going to analyze the Dom' solution of this problem.
My code was :
| Code: |
long crc = 1;
for (int y = 0; y < 9; y ++)
{
long tmp = 1;
for (int x = 0; x < 9; x++)
{
c = this.cells[x][y];
int n = c.getNumber();
if (n != 0)
{
tmp = (tmp << n);
}
else
{
return false;
}
}
crc += (tmp) >> y ;
}
return (crc == 0x3FE000000001L);
|
|
|
| Back to top |
|
|
| jemore2
| | Joined: 02 Feb 2006 | | Posts: 4 | | : | |
Items |
|
| Posted: Fri Feb 03, 2006 6:27 pm Post subject: |
|
|
| dom wrote: |
(...)
My recommendation would be to just cycle through each house and count instances of each digit in a 9 value array. (...)
|
What do you call a house ? Is it what i call a "sector" ? (not the row, not the column, but the small 3x3 square)
I'm going to test your solution. |
|
| Back to top |
|
|
| jemore2
| | Joined: 02 Feb 2006 | | Posts: 4 | | : | |
Items |
|
| Posted: Fri Feb 03, 2006 7:05 pm Post subject: |
|
|
Ok, I come with my solution. It is small in memory and fast.
(What i mean by small memory, is that .class filesize must be as small as possible. So code size must be short). Inspired by Dom's suggestion
| Code: |
Cell c;
int n;
byte[] nums = {0,0,0, 0,0,0, 0,0,0};
for(int y = 0; y < 9; y++)
{
for (int x = 0; x < 9 ; x++)
{
// Check line
c = this.cells[x][y];
n = c.getNumber();
if (n == 0)
{ // Cell not setted by the user
return false;
}
nums[n-1]++;
// Check rows
c = this.cells[y][x];
n = c.getNumber();
if (n == 0)
{ // Cell not setted by the user
return false;
}
nums[n-1]++;
}
}
for (int y = 0; y < 9; y++)
{
if (nums[y] != 18)
return false;
}
return true;
|
|
|
| Back to top |
|
|
| dom
| | Joined: 10 Nov 2005 | | Posts: 42 | | : | |
Items |
|
| Posted: Mon Feb 06, 2006 10:07 am Post subject: |
|
|
Hi jemore,
Glad you got your checker working. By "house" I mean any row, column or region. I think my "region" is most analagous to your "sector".
Also, looking at your pseudocode I'm not sure this will work. Imagine this basic grid
123 456 789
789 564 123
456 789 231
....
If I swap the 1,7 on column 1 I get...
723 456 789
189 564 123
456 789 231
....
I'm fairly certain that your code will still think this is valid as the counts for digits in rows and columns will be the same in total. You really need to check the count after each cycle through a column or row. You will also need to check each region (sector) too or there are some cases that will slip through.
You might also want to take a look at some of the entries in the smallest sudoku solver thread in programming sudoku as these programmers have developed some very small and quick tests for correctness.
Hope that helps.
_________________
Orangeminds Sudoku
http://www.orangeminds.com/sudoku/ |
|
| Back to top |
|
|
| hopeforestcom
| | Joined: 05 Feb 2006 | | Posts: 2 | | : | |
Items |
|
| Posted: Tue Feb 07, 2006 1:48 pm Post subject: |
|
|
I think it is not a efficient way by filling 1-9 , if you wanna save your memory and time.
1st,let us think about it .what is different between 123456789 and 12345678? Nothing! So ,we just need 12345678. Right?
2nd, Denote 1 in 00000001,2 in 00000010,3 in 00000100, ...... and so on.
you just do "||" "or" operation for each block, culomn and row, it is fast . and don't waste any memory.
I hope it can help you. Good luck!
==============================
hopeforestcom@gmail.com
A new free sudoku solver
Hi, I am Robin from montreal,Canada
I wrote a free sudoku solver.
Please try it.
http://www.hopeforest.com/download/download.html
_________________
Hi, I am Robin from montreal,Canada
I wrote a free sudoku solver.
Please try it.
http://www.hopeforest.com/download/download.html |
|
| Back to top |
|
|
| neeta
| | Joined: 08 Feb 2006 | | Posts: 2 | | : | |
Items |
|
| Posted: Wed Feb 08, 2006 2:47 pm Post subject: checking for correctness of sudoku grid |
|
|
| Can anyone help me write a program in Ada/C to check if the sudoku grid that is entered is correct or not. |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron |
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
