|
| View previous topic :: View next topic |
| Author |
Message |
| Moorst
| | Joined: 24 Nov 2008 | | Posts: 6 | | : | |
Items |
|
 Posted: Wed Mar 18, 2009 7:26 pm Post subject: CRME working, trying to implement techniques (Java) |
 |
|
Hello, I'm in the process of creating a Sudoku game for my project, and the first step is to create the solver. I have recently managed to implement the Column, Row, Mini-grid elimination into the solver, which would be the first algorithm the solver would use, then followed by other techniques such as naked singles/doubles etc, and eventually algorithms such as X-Wing.
Eventually the solver should use various techniques to solve any puzzle (or so i hope). I know that using brute force would be the simplest option, but I must use logical techniques to create the solver.
I'm a bit stuck as of where to start. I would like to get the easiest algorithms implemented first, so I imagine the naked singles would be the first to start on.
For the Naked Singles, I believe I need to:
- Find the possibilities for every cell
- Compare the possibilities in every row, column and mini-grid
- Identify the naked singles, and store them to related cell
- Rinse and repeat
Is this correct?
My CRME algorithm looks like this:
[code]
public void CRME()
{
changed= true;
while (changed)
{
changed = false;
for (row = 0; row < gridlength; row++)
{
for (column = 0; column < gridlength; column++)
{
if (grid[row][column] == 0)
{
checkRow();
checkColumn();
checkSquare();
Systemoutprintln("Candidates for cell "+cellNumber+": "+poss);
int count = posssize();
if (count == 1)
{
Integer x=(Integer)possget(0);
int answer = xintValue();
grid[row][column] = answer;
changed = true;
}
cellNumber++;
resetPossibilities();
}
else
{
cellNumber++;
}
}
}
}
}
(Note I have removed all '.'s from the code, as it wouldn't let me post with them, as apparently I'm trying to post a url!)
[/code]
It simply iterates through every cell in the grid, checking the row, column and mini-grid of a cell, and removing the numbers found from an arraylist called 'poss' (poss is constantly reset for every cell). If a cell has just one possibility, then that number is stored into the cell, and the status of the grid is set to changed. If changed is true, then the CRME is run again, until the algorithm is run and the grid doesn't change, this is when the next algorithms needs to be ran.
As you can see, I think out of the 4 points I made earlier, I have the first 2 done. So therefore I need some help to create a way to identify the singles, and store them to the cell.
I also have the problem with moving onto the next algorithm when the current one is exhausted. What would be the easiest way to do this?
If I have not explained myself enough, or if here is more code you need to help me progress with this project, please let me know. I appreciate any help that comes my way, thank you for reading. |
|
| Back to top |
|
 |
| Lunatic
 | | Joined: 11 Mar 2007 | | Posts: 166 | | : | | Location: Ghent - Belgium |
Items |
|
| Posted: Wed Mar 18, 2009 10:37 pm Post subject: Re: CRME working, trying to implement techniques (Java) |
|
|
| Moorst wrote: | | I know that using brute force would be the simplest option, but I must use logical techniques to create the solver. |
If all logical techniques fail to solve the sudoku then you will need brute force to solve it. Except for the easiest sudokus, you may need brute force to rapidly check if a sudoku has one unique solution.
| Moorst wrote: | | I'm a bit stuck as of where to start. I would like to get the easiest algorithms implemented first, so I imagine the naked singles would be the first to start on. |
Some prefer hidden singles as first lookup routine, they are easier to spot when not using pencilmarks.
| Moorst wrote: | For the Naked Singles, I believe I need to:
- Find the possibilities for every cell
- Compare the possibilities in every row, column and mini-grid
- Identify the naked singles, and store them to related cell
- Rinse and repeat
Is this correct?
|
You just have to:
- Count the possibilities for each cell
- If a cell is encountered with only one possibility, store that possibility as that cell's solution
- Rinse and repeat with the first solving technique
For hidden singles (the most human-like solving way):
- For each box count the cells for each unsolved possibility
- if only 1 cell in that box has a certain possibility, store that possibility as that cell's solution
- Rinse and repeat with the first solving technique
- do the same for rows and columns
The next technique(s) should be Locked Candidates followed by Naked and/or Hidden Subsets
For more advanced techniques you will need pencilmarks or something similar.
| Moorst wrote: |
| Code: | public void CRME()
{
changed= true;
while (changed)
{
changed = false;
for (row = 0; row < gridlength; row++)
{
for (column = 0; column < gridlength; column++)
{
if (grid[row][column] == 0)
{
checkRow();
checkColumn();
checkSquare();
Systemoutprintln("Candidates for cell "+cellNumber+": "+poss);
int count = posssize();
if (count == 1)
{
Integer x=(Integer)possget(0);
int answer = xintValue();
grid[row][column] = answer;
changed = true;
}
cellNumber++;
resetPossibilities();
}
else
{
cellNumber++;
}
}
}
}
} |
It simply iterates through every cell in the grid, checking the row, column and mini-grid of a cell, and removing the numbers found from an arraylist called 'poss' (poss is constantly reset for every cell). If a cell has just one possibility, then that number is stored into the cell, and the status of the grid is set to changed. If changed is true, then the CRME is run again, until the algorithm is run and the grid doesn't change, this is when the next algorithms needs to be ran.
|
What you call a "mini-grid" is normally called a "box". I don't see what the use is of checkRow() checkColumn() and checkSquare().
Maybe you should use an integer array to hold the possible candidates for each cell in a bitwise manner, this opens the possibility to easy check for naked singles. And you can use that array for other techniques as well.
Since you are adressing the grid both column and row related you can use an array like Candidates[row][column]. If candidate 1 is a possibility then bit 0 must be set, If candidate 2 is a possibility then bit 1 must be set, and so on...
Based upon the possibilities you can have values between 0 and 511 whereof 0 will mean that the cell is solved, and whereof 511 will mean that all values are still possible for that cell. The values 1, 2, 4, 8, 16, 32, 64, 128 and 256 will indicate that there is only one possibility for that cell.
Whenever you want to solve a new sudoku this array must be initiated first, like this:
| Code: |
{
for (row = 0; row < gridlength; row++)
{
for (column = 0; column < gridlength; column++)
{
Candidates[row][column] = 511;
}
}
for (row = 0; row < gridlength; row++)
{
for (column = 0; column < gridlength; column++)
{
if (grid[row][column]>0)
{
int answer = grid[row][column];
Update_Candidates(row, column, answer);
}
}
}
}
|
It's obvious that the routine called Update_Candidates must erase the bit representing argument 'answer', in array Candidates[][] for all cells sharing the same row, column and box with the cell referred to by arguments 'row' and 'column', AND clear the referred cell's candidates by following statement: Candidates[row][column]=0;
You can use another pre-filled array (for example: CountCandidates[]) who will return the number of candidates (bits) when feeded with Candidates[row][column]. That array must have 512 elements (from 0 to 511). You must fill this array at program start with these values:
CountCandidates[0] = 0
CountCandidates[1] = 1
CountCandidates[2] = 1
CountCandidates[3] = 2
CountCandidates[4] = 1
CountCandidates[5] = 2
CountCandidates[6] = 2
CountCandidates[7] = 3
CountCandidates[8] = 1
CountCandidates[9] = 2
CountCandidates[10] = 2
CountCandidates[11] = 3
CountCandidates[12] = 2
and so on...
...
...
until...
CountCandidates[508] = 7
CountCandidates[509] = 8
CountCandidates[510] = 8
CountCandidates[511] = 9
You can easely fill this array in a small for-next loop like this:
| Code: |
For (int i=0;i<512;i++)
{
int j=i;
CountCandidates[i]=0;
While (j>0)
{
If (j%2) Then CountCandidates[i]++;
j=j/2;
}
}
}
|
j%2 will give the reminder for j/2. If j is even than the reminder will be 0, if j is not even than the reminder will be 1.
Using these two arrays, your code could look like this:
| Code: |
public void CRME()
{
changed= true;
while (changed)
{
changed = false;
for (row = 0; row < gridlength; row++)
{
for (column = 0; column < gridlength; column++)
{
if (CountCandidates[Candidates[row][column]] == 1)
{
int j = Candidates[row][column];
int answer = 0;
while (j>0)
{
if j%2 then answer++;
j = j/2;
}
grid[row][column] = answer;
Update_Candidates(row, column, answer);
changed = true;
}
}
}
}
}
|
| Moorst wrote: | | I also have the problem with moving onto the next algorithm when the current one is exhausted. What would be the easiest way to do this? |
Make a routine for each solving technique, and let it return a value to distinguise if the technique was succesfull (value 1) or not (value 0). Based upon an indicator (example: Technique) you must call your techniques. If the indicator = 1 then the technique for Naked Singles is called, if the indicator is 2 then the technique for Hidden Singles is called, if the indicator is 3 then the next technique is called, and so on...
If a technique was succesfull then the indicator must be reset to 1, if a technique was unsuccesfull then the indicator must be incremented. Your last technique must set your indicator to 0 if it was unsuccesfull, in order to break the loop. Then the indicator must be evaluated....
| Code: |
int Technique=1;
while (Technique>0)
{
switch (Technique)
{
case 1
if (Naked_Single()==1) Technique=1 else Technique++;
case 2
if (Hidden_Single()==1) Technique=1 else Technique++;
case 3
if (Another_Technique()==1) Technique=1 else Technique++;
case 4
if (Last_Technique()==1) Technique=1 else Technique=0;
}
}
|
_________________
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
