|
| View previous topic :: View next topic |
| Author |
Message |
| redtan
| | Joined: 06 Nov 2008 | | Posts: 5 | | : | |
Items |
|
 Posted: Fri Nov 07, 2008 3:50 pm Post subject: Need Help Programming Naked/Hidden Subsets |
 |
|
I'm writing a program that can solve Sudoku puzzle with human technique. So far, I have no problem implementing basic techniques. But, I have problems coding Naked/Hidden Subsets.
I've found bitwise approach to find Naked/Subsets but it seems too complicated for me. I'm looking for other efficient algorithm that can find Naked/Hidden Subsets.
Please help... |
|
| Back to top |
|
 |
| mrmarky2
| | Joined: 13 Jan 2007 | | Posts: 64 | | : | |
Items |
|
| Posted: Fri Nov 07, 2008 4:34 pm Post subject: |
|
|
Hi,
I dont know what this bitwise approach is, I did mine a different way. I have a seperate algorithm for each Single/Pair/Triple... which is probably not the best way to do it. Im gonna rewrite it later to cut down on code.
Well heres how I find naked pairs, i'm not giving any code yet, because your probably writing in a different language.
My Information is stored in an nxn and a nxnxn array. So for 9x9 sudoku a 9x9 and a 9x9x9 array. I wrote my code so that I will find naked/hidden pairs in any size sudoku.
The 9x9 array stores what values are in the cell, 0-8. 9 means it has nothing in it. The 9x9x9 array stores whether each number can go in each cell. So for the cell 5 across and 6 down the array, Pencilmarks[4][5][7] (the 9x9x9 array), tells me whether 8's can go in that cell. 0 if it can, 1 if it can't.
I have 2 functions, the first passes cell coordinates to the second. The second see's if theres a naked pair in them.
Heres the first function steps:
Pass the coordinates of box 1 to the second function.
Then box 2, all the way to 9
Pass the coordinates of row 1 to the second function.
Then row 2, all the way to 9.
Pass the coordinates of column 1 to the second function.
Then column 2, all the way to 9.
The second function:
Takes the 9 coordinates, findes all the cells with only two possibilities in, so two of the cells that have 0 value in the Pencilmarks array.
Then it goes through each combination of 2 squares and sees to see if there are 2 squares that only take the same 2 numbers. If so you have found a naked pair. Go through each of the coordinates passed to function 2 and make sure all of there Pencilmarks[][][] of the 2 values are set to 1.
Hope this helps. I can give you some code if you want, but its c++,
Mark |
|
| Back to top |
|
|
| Lunatic
 | | Joined: 11 Mar 2007 | | Posts: 166 | | : | | Location: Ghent - Belgium |
Items |
|
| Posted: Fri Nov 07, 2008 6:46 pm Post subject: |
|
|
For 9x9 sudokus, consider 2 basic arrays:
Solution(0 to 80), holding the value for each solved cell, and 0 for each unsolved cell.
CellsCandidates(0 to 80), holding the bitwise candidates for each unsolved cell, and 0 for each solved cell.
If candidate 1 is present then bit 0 is set
If candidate 2 is present then bit 1 is set
And so on...
Best is to create another static array to easely return the number of candidates in a cell.
This array must have 512 elements (0 to 511). Example: CountCandidates(0 to 511)
You can easely fill this array at program start by doing the following:
| Code: | For i = 0 To 511
CountCandidates(i) = 0
j = i
Do While j > 0
If (j Mod 2) Then CountCandidates(i) = CountCandidates(i) + 1
j = (j - (j Mod 2)) / 2
Loop
Next i
|
In your code, CountCandidates(CellsCandidates(Any_Cell)) will return the number of candidates from Any_Cell.
In my solver i created a function like this:
| Code: | Function NakedPair() As Boolean
NakedPair = False 'set return value to unsuccesfull
For i = 0 To 8 'each row
For ii% = 0 To 7 'first cell
For jj% = (ii% + 1) To 8 'second cell
'check if both cells are unsolved
If (Solution((i * 9) + ii%) = 0) _
And (Solution((i * 9) + jj%) = 0) Then
'check if common candidates equals 2 (2 candidates for 2 cells)
If CountCandidates(CellsCandidates((i * 9) + ii%) _
Or CellsCandidates((i * 9) + jj%)) = 2 Then
'rescan all cells from the current row
For j = 0 To 8
'cell j must be different from cells ii% and jj%, must be unsolved,
'and must have at least one of the common
'candidates from cells ii% and jj%
If (j <> ii%) And (j <> jj%) _
And (Solution((i * 9) + j) = 0) _
And CountCandidates(CellsCandidates((i * 9) + ii%) _
And CellsCandidates((i * 9) + jj%) _
And CellsCandidates((i * 9) + j)) Then
'if you reached this stage, you spotted a naked pair (ii% and jj%)
'in row i with at least one cell (j) that will loose one or
'more candidates common to the naked pair
'remove candidates from cell j common to the naked pair
CellsCandidates((i * 9) + j) = CellsCandidates((i * 9) + j) And _
Not (CellsCandidates((i * 9) + ii%) _
Or CellsCandidates((i * 9) + jj%))
NakedPair = True 'set return value to succesfull
End If
Next j
'check if eliminations were made, and if so exit function
If NakedPair Then Exit Function
End If
End If
Next jj%
Next ii%
next i
'do the same for columns and boxes
End Function
|
for naked triples you can easely expand the code from naked pairs to:
| Code: | Function NakedTriple() As Boolean
NakedTriple = False 'set return value to unsuccesfull
For i = 0 To 8 'each row
For ii% = 0 To 6 'first cell
For jj% = (ii% + 1) To 7 'second cell
For kk% = (jj% + 1) To 8 'third cell
'check if these three cells are unsolved
If (Solution((i * 9) + ii%) = 0) _
And (Solution((i * 9) + jj%) = 0) _
And (Solution((i * 9) + kk%) = 0) Then
'check if common candidates equals 3 (3 candidates for 3 cells)
If CountCandidates(CellsCandidates((i * 9) + ii%) _
Or CellsCandidates((i * 9) + jj%) _
Or CellsCandidates((i * 9) + kk%)) = 3 Then
'rescan all cells from the current row
For j = 0 To 8
'cell j must be different from cells ii%, jj% and kk%, must be unsolved,
'and must have at least one of the common
'candidates from cells ii%, jj% and kk%
If (j <> ii%) And (j <> jj%) And (j <> kk%) _
And (Solution((i * 9) + j) = 0) _
And CountCandidates(CellsCandidates((i * 9) + ii%) _
And CellsCandidates((i * 9) + jj%) _
And CellsCandidates((i * 9) + kk%) _
And CellsCandidates((i * 9) + j)) Then
'if you reached this stage, you spotted a naked triple (ii%, jj% and kk%)
'in row i with at least one cell (j) that will loose one
'or more candidates common to the naked triple
'remove candidates from cell j common to the naked triple
CellsCandidates((i * 9) + j) = CellsCandidates((i * 9) + j) And _
Not (CellsCandidates((i * 9) + ii%) _
Or CellsCandidates((i * 9) + jj%) _
Or CellsCandidates((i * 9) + kk%))
NakedTriple = True 'set return value to succesfull
End If
Next j
'check if eliminations were made, and if so exit function
If NakedTriple Then Exit Function
End If
End If
Next kk%
Next jj%
Next ii%
next i
'do the same for columns and boxes
End Function
|
Keep in mind that in my examples the sudoku cells are adressed from 0 (top left) to 80 (bottom right), like this:
| Code: | 00 01 02 03 04 05 06 07 08
09 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 56 57 58 59 60 61 62
63 64 65 66 67 68 69 70 71
72 73 74 75 76 77 78 79 80 |
Rows are numbered 0 to 8 from top to bottom
Columns are numbered 0 to 8 from left to right
For example: the adress of the cell in row X column Y is calculated:
(X * 9) + Y
Boxes are numbered 0 to 8 from top left to bottom right like this:
0 1 2
3 4 5
6 7 8
...and cells in a box likewise.
So, adressing the cells related to the boxes can be tricky, therefore another static array can be made and filled at program start to make things easy. For example:
BoxCellnumbers (0 to 8, 0 to 8)
The first dimension refers to the box and the second dimension to the cell.
Filling this array can be done like this:
| Code: |
For i = 0 To 2
For j = 0 To 2
For k = 0 To 2
For l = 0 To 2
Cell = (j * 27) + (i * 3) + (l * 9) + k
Box = (j * 3) + i
BoxCellnumbers(Box, (l * 3) + k) = Cell
Next l, k
Next j, i
|
Now BoxCellnumbers(Any_Box, Any_Cell) will return the adress from Any_Cell related to Any_Box
Hidden subsets are handled a slightly different, i will post that later...
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~ |
|
| Back to top |
|
|
| redtan
| | Joined: 06 Nov 2008 | | Posts: 5 | | : | |
Items |
|
| Posted: Sat Nov 08, 2008 2:43 am Post subject: |
|
|
Thanks lunatic for your reply..
But, I'm looking for a non-bitwise approach, since I store possible candidate for each cell in a string. I store the possible candidate for all cells in array of string.
for example if cell (2,2) has possible candidate 1|4|5
so the array possible[1][1]="145"
Thx, anyway... |
|
| Back to top |
|
|
| briturner
| | Joined: 14 Oct 2008 | | Posts: 75 | | : | |
Items |
|
| Posted: Sat Nov 08, 2008 3:01 am Post subject: |
|
|
You are actually very close to a bitwise representation, you may want to think about going all the way.
instead of storing "145", think of it stored as storing a string of 1 or 0 based on if the number is included. if each 9 numbers are in the position as follows "987654321", then 145 would be equal to "000011001" (where the position for 5, 4, and 1 are set to 1, everything else is 0). That is all the bitwise representation is.
Doing so adds a lot of elegant solutions that are difficult when using strings.
brit |
|
| Back to top |
|
|
| mrmarky2
| | Joined: 13 Jan 2007 | | Posts: 64 | | : | |
Items |
|
| Posted: Sat Nov 08, 2008 11:04 am Post subject: |
|
|
| Quote: | | In my solver i created a function like this: |
Your code is a slightly long way of doing it, you have a copy of your code for each a row column and box. If you want to add extra constraints then you have to add another copy of your code.
Heres what I did:
The first function:
| Code: |
void wxSudoku::NakedPairs()// in this we pass coordinates of each row to another function to check them for naked pairs.
{
int once=0;
int hold[width][2]//width is the length of the grid
for(int i=0; i<width; i++)//checks boxes
{
if(once==0)
{
for(int j=0; j<width; j++)
{
hold[j][0]=boxes[i][j][0];//boxes holds all the coordinates of the cells in each box. Useful to do it this way because to change the code to jigsaw sudoku you only have to change the boxes array about.
hold[j][1]=boxes[i][j][1];
}
bool check=FindNakedPairs(hold);
if(check)once++;//if it finds a naked pair stop straight away.
}
}
for(int i=0; i<width; i++)//naked pairs in rows
{
if(once==0)
{
for(int k=0; k<width; k++)
{
hold[k]=i;
hold[k]=k;
}
bool check=FindNakedPairs(hold);
if(check)once++;
}
}
for(int i=0; i<width; i++)//naked pairs in columns
{
if(once==0)
{
for(int k=0; k<width; k++)
{
hold[k]=k;
hold[k]=i;
}
bool check=FindNakedPairs(hold);
if(check)once++;
}
}
}
|
The second that finds the naked pairs:
| Code: |
bool wxSudoku::FindNakedPairs(int hold[width][2])
{
int once=0;
int num[width][4];
int counter=0;
int counter2=0;
//Step1 find cells with only 2 values in.
for(int k=0; k<width; k++)//go through each cell
{
if(Cell[num2[k][0]][num2[k][1]] == width)//cell hasn't got a number in already.
{
int counter1=0;
int onecatch=0;
int twocatch=0;
for(int m=0; m<width>1 && counter>2)//if more than 1 cell has only 2 numbers that can go in it and there are more than 2 cells left in the 9 passed to this function, then there could be a naked pair.
{
for(int l=0; l<counter2-1; l++)
{
for(int q=0; q<counter2; q++)// go through each combination of cells to find two that only take the same two values
{
if(l<q && num[l][2]==num[q][2] && num[l][3]==num[q][3] && once==0)//tests to see if the two cells picked take the 2 same values. if so then theres a naked pair.
{
counter=0;
for(int p=0; p<width; p++)
{
int u=hold[p][0];
int v=hold[p][1];
for(int m=0; m<2; m++)//deletes any of these numbers from the other 9 cells
{
if(Pencilmark[u][v][num[l][m+2]] == 0 && Cell[u][v] == width && (u != num[l][0] || v != num[l][1]) && (u != num[q][0] || v != num[q][1]))
{
counter++;
Pencilmark[u][v][num[l][m+2]]++;
}
}
}
if(counter!=0)once++;
}
}
}
}
return once;//returns 1 if a naked pair is found.
}
|
|
|
| Back to top |
|
|
| Lunatic
| | Joined: 11 Mar 2007 | | Posts: 166 | | : | | Location: Ghent - Belgium |
Items |
|
| Posted: Sun Nov 09, 2008 12:55 pm Post subject: |
|
|
| mrmarky2 wrote: | | Lunatic wrote: | | In my solver i created a function like this: |
Your code is a slightly long way of doing it, you have a copy of your code for each a row column and box. If you want to add extra constraints then you have to add another copy of your code. |
How about this:
| Code: | Function NakedPair() As Boolean
NakedPair = False 'set return value to unsuccesfull
For i = 0 To (CountHouses - 1) '(rows, columns, boxes or jigsaw cages, diagonals, etc...)
For ii% = 0 To 7 'first cell
For jj% = (ii% + 1) To 8 'second cell
'check if both cells are unsolved
If (Solution(CellsHousenumber(i, ii%)) = 0) _
And (Solution(CellsHousenumber(i, jj%)) = 0) Then
'check if common candidates equals 2 (2 candidates for 2 cells)
If CountCandidates(CellsCandidates(CellsHousenumber(i, ii%)) _
Or CellsCandidates(CellsHousenumber(i, jj%)) = 2 Then
'rescan all cells from the current row
For j = 0 To 8
'cell j must be different from cells ii% and jj%, must be unsolved,
'and must have at least one of the common
'candidates from cells ii% and jj%
If (j <> ii%) And (j <> jj%) _
And (Solution(CellsHousenumber(i, j)) = 0) _
And CountCandidates(CellsCandidates(CellsHousenumber(i, ii%)) _
And CellsCandidates(CellsHousenumber(i, jj%)) _
And CellsCandidates(CellsHousenumber(i, j))) Then
'if you reached this stage, you spotted a naked pair (ii% and jj%)
'in row i with at least one cell (j) that will loose one or
'more candidates common to the naked pair
'remove candidates from cell j common to the naked pair
CellsCandidates(CellsHousenumber(i, j)) = CellsCandidates(CellsHousenumber(i, j)) And _
Not (CellsCandidates(CellsHousenumber(i, ii%)) _
Or CellsCandidates(CellsHousenumber(i, jj%)))
NakedPair = True 'set return value to succesfull
End If
Next j
'check if eliminations were made, and if so exit function
If NakedPair Then Exit Function
End If
End If
Next jj%
Next ii%
next i
End Function |
Where CountHouses is the total sum of houses (rows, columns, boxes or jigsaw cages, etc...) depending on the type of sudoku, and the array CellsHousenumber (0 to (CountHouses - 1), 0 to 8) is the adressholder for each cell in each available house.
But the reason why i keep the rows, columns, cages seperately in my program MPQ Sudoku is for the "Hint" and "AutoSolve" functions. Even the code i provided in the post you are referring to, is not the actual code i use in my program, but an adaption of it to make it more readable and understandable for anyone. In my real code that function is named NakedHidden, has to be called with some arguments, and handles both naked and hidden subsets from pairs to quints.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~ |
|
| Back to top |
|
|
| Lunatic
| | Joined: 11 Mar 2007 | | Posts: 166 | | : | | Location: Ghent - Belgium |
Items |
|
| Posted: Thu Nov 13, 2008 7:16 pm Post subject: |
|
|
@redtan
Since you're not interested in bitwise operations, i can't see the use of posting some hidden single lookup code, unless you changed your mind
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~ |
|
| 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
