| View previous topic :: View next topic |
| Author |
Message |
| Moorst
| | Joined: 24 Nov 2008 | | Posts: 6 | | : | |
Items |
|
 Posted: Wed Apr 29, 2009 3:43 am Post subject: Problems with brute force alg |
 |
|
Currently trying to get my brute force algorithm working:
| Code: |
public void bruteForce()
{
if (BF_on = true)
System.out.println("Brute Force Algorithm Initiated");
changed = true; //means change has occured within grid, reset to col-0,row-0
while (changed)
{
changed = false;
for (row = 0; row < 9; row++)
{
for (column = 0; column < 9; column++) //iterate through grid
{
if (grid[row][column] == 0) //if cell is empty
{
for (int i = 1; i <= 9; i++) //1-9 are possible entries
{
checkRow(); //find cell possibilities
checkColumn();
checkSquare();
System.out.println("Candidates for cell: "+poss);
if (poss.contains(i)) //if the current entry is in the cells possiblity arraylist
{
int count = poss.size();
if (count >= 1)
{
System.out.println(i+" stored to cell "+cellNumber);
changed = true;
grid[row][column] = i; //store entry to cell
}
else if(count == 0)
{
grid[row][column--] = 0; //if cell has no possiblities, grid must be invalid, so go back to prev cell, and store
next highest value
i++;
resetPossibilities();
}
}
resetPossibilities();
}
}
}
}
if (isComplete())
{
changed = false;
System.out.println("Grid Solved!"); //if no empty cells left, grid is solved
}
else
{
//should i reset the grid here?
}
}
BF_on = false;
System.out.println("Brute Force Algorithm Exhausted");
} |
Sorry for the messy code, and for some reason whenever i use the 'lessthan' or 'greaterthan' signs it skips loads of my code out of the post... anyways...
The problem i'm having is skipping back to the previous cell and changing the value, so that it has an affect on the rest of the grid and produces a valid result.
At the moment, I'm getting this for an empty grid:
| Code: |
-----------------------
| 9 8 7 | 6 5 4 | 3 2 1 |
| 6 5 4 | 9 8 7 | _ _ _ |
| 3 2 1 | _ _ _ | 9 8 7 |
-----------------------
| 8 9 6 | 7 4 5 | 2 3 _ |
| 7 4 5 | 8 9 6 | 1 _ _ |
| 2 3 _ | 1 _ _ | 8 9 6 |
-----------------------
| 5 7 9 | 4 6 8 | _ 1 3 |
| 4 6 8 | 5 7 9 | _ _ 2 |
| 1 _ 3 | 2 _ _ | 7 6 9 |
-----------------------
|
It's obvious that it won't put values in the cells because it would mean the grid would have the same number in the same col, row or box (that's what the check methods do), and I'm really having trouble getting my head around what I must do. I know I haven't coded it in the best possible way, but I use lots of other algorithms in the same 'way' and would love to be able to get this working with the help of you geniuses :D.
Can anyone help me out?
Do I need to do something within the else statement inside the for loop, to move back to the prev cell? (column-- isnt working)
Or do I need to reset the whole grid after one loop through and start in a different place, or with a different value?
Thank you for your time
Last edited by Moorst on Wed Apr 29, 2009 1:28 pm; edited 1 time in total |
|
| Back to top |
|
 |
| hobiwan
| | Joined: 11 Feb 2008 | | Posts: 83 | | : | |
Items |
|
| Posted: Wed Apr 29, 2009 5:57 am Post subject: |
|
|
Moorst,
if you want to post code you have to check "Disable HTML in this post". |
|
| Back to top |
|
|
| Moorst
| | Joined: 24 Nov 2008 | | Posts: 6 | | : | |
Items |
|
| Posted: Wed Apr 29, 2009 1:29 pm Post subject: |
|
|
| Sorry about that, I've edited the main post now. Can anyone help me out? |
|
| Back to top |
|
|
| hobiwan
| | Joined: 11 Feb 2008 | | Posts: 83 | | : | |
Items |
|
| Posted: Thu Apr 30, 2009 6:02 am Post subject: |
|
|
I didnt try it, but reading your code a few things come to mind:
When a cell is set, you should immediately proceed to the next cell
When a cell has no possibilities left, you should break from the inner loop and backtrack
You decrement column, but the for loop increments it immediately again, so you end up with the same cell again
I cant see a back tracking in the rows |
|
| Back to top |
|
|
| Lunatic
 | | Joined: 11 Mar 2007 | | Posts: 166 | | : | | Location: Ghent - Belgium |
Items |
|
| Posted: Thu Apr 30, 2009 10:08 am Post subject: |
|
|
You can check out this post (click) where you can find a brief explanation of a simple brute force solving approach, and some related links.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~ |
|
| Back to top |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
