# Brute force Sudoku algorithm is not working

• April 18th, 2012, 05:17 PM
cbeberge
Brute force Sudoku algorithm is not working
Hi

I have squeezed my brain for 2 days now to find the bug that bugs with my code. Iam trying to develop a brute force sudoku solver, but the sudoku algorithm wont work. Please give me some help, i really need to find a solution.

Under is the entire Square(cell) class where the algorithm finds its place, here it will recursive call next square.

**4x4 Sudoku board INPUT**

0 2 | 1 3
0 0 | 0 4
---------
0 0 | 0 1
0 4 | 3 2

**Expected OUTPUT**

4 2 | 1 3
3 1 | 2 4
---------
2 3 | 4 1
1 4 | 3 2

**Actually OUTPUT**

4 2 | 1 3
2 4 | 3 4
---------
3 0 | 0 1
0 4 | 3 2

Code :

```public abstract class Square {   private Square next;   private Box box; private Row row; private Columne columne;   private int value;   Square(int value, Box box, Row row, Columne columne) { this.value = value; this.box = box; this.row = row; this.columne = columne; }   boolean setNumberMeAndTheRest(Board board) {   Board original = board;   if(getNext() == null) { for(int i = 1; i <= board.getDimension(); i++) { if(legalValue(i)) { setValue(i); } } board.saveSolution();   } else { if(this instanceof DefinedSquare) { getNext().setNumberMeAndTheRest(board);   } else { for(int i = 1; i <= board.getDimension(); i++) { if(legalValue(i)) { setValue(i);   if(getNext().setNumberMeAndTheRest(board)) { return true; } else { setValue(i); } } } board = original; return false; } } board = original; return false; }   int getValue() { return value; }   void setValue(int value) { this.value = value; }   void setNext(Square next) { this.next = next; }   public Square getNext() { return next; }   /** * Checks if value is legal in box, row and column. * @param value to check. * @return true if value is legal, else false. */ boolean legalValue(int value) { if(box.legalValue(value) && row.legalValue(value) && columne.legalValue(value)) { return true; } return false; } }```
• April 18th, 2012, 06:44 PM
pbrockway2
Re: Brute force Sudoku algorithm is not working
I haven't looked that closely (you seem to have code missing), but this caught my eye:

Code :

```boolean setNumberMeAndTheRest(Board board) { Board original = board;   // things are then done with board, possibly changing its state. // but board is not assigned a new value   board = original; // why? since board==original anyway return /*whatever*/ }```

Since board is not assigned a different value at any point, it isn't clear what is going on with the original variable. In particular it is not "restoring" anything.

Code :

```import java.awt.Point;   public class Foo { public static void main(String[] args) throws Exception { Point foo = new Point(666, 42); System.out.println("foo starts as " + foo);   Point original = foo;   foo.setLocation(0, 0); System.out.println("foo now " + foo);   foo = original; System.out.println("foo ends up as " + foo); } }```
• April 18th, 2012, 07:46 PM
aussiemcgr
Re: Brute force Sudoku algorithm is not working
Out of curiosity, why are you attempting to do the entire thing with brute force (assignment?)? I wrote a Sudoku Solver Algorithm a few years ago and I found it easier to do the basic checks (row/column/box) for guaranteed answers, and then only do brute force when I ran out of guaranteed answers. Kinda like how a human would do it.
• April 19th, 2012, 06:18 AM
cbeberge
Re: Brute force Sudoku algorithm is not working
The task is to make a brute force algorithm. Sorry, but this with original board was just something that I test and forgot to remove, her is the algorithm the way should bee in the first post.

Code :

```boolean setNumberMeAndTheRest(Board board) {   if(getNext() == null) { for(int i = 1; i <= board.getDimension(); i++) { if(legalValue(i)) { setValue(i); } } board.saveSolution();   } else { if(this instanceof DefinedSquare) { getNext().setNumberMeAndTheRest(board);   } else { for(int i = 1; i <= board.getDimension(); i++) { if(legalValue(i)) { setValue(i);   if(getNext().setNumberMeAndTheRest(board)) { return true; } else { setValue(i); } } } return false; } } return false; }```
• April 19th, 2012, 09:16 AM
aussiemcgr
Re: Brute force Sudoku algorithm is not working
How confident are you that the legalValue(int value) method is working correctly?
• April 19th, 2012, 03:31 PM
cbeberge
Re: Brute force Sudoku algorithm is not working
I´m pretty sure that legalValue(int value) works, under is the code for the function:

Code :

``` boolean legalValue(int value) { if(row.legalValue(value) && columne.legalValue(value) && box.legalValue(value)) { return true; } return false; }```

After a long day I have finally got a step closer a perfectly working solution, the algorithm below works for some types of sudoku board, but not all.

It works for this 4 x 4 board.

0 0 | 1 0
0 3 | 0 4
----------
3 0 | 4 0
0 2 | 0 0

that has only one solution, namely

2 4 | 1 3
1 3 | 2 4
----------
3 1 | 4 2
4 2 | 3 1

On this 9 x 9 board that has 28 solutions throw out the algorithm, 1 wrong solution

0 0 1 | 0 0 3
0 0 0 | 0 0 0
--------------
0 0 0 | 0 2 0
2 6 0 | 0 0 0
--------------
0 0 0 | 3 0 0
3 0 0 | 1 0 2

the algorithm gives us

4 2 1 | 5 6 3
6 3 4 | 2 1 5
--------------
1 5 3 | 6 2 4
2 6 5 | 4 3 1
--------------
5 1 2 | 3 4 6
3 4 6 | 1 5 2

Her is the partially acting algorithm

Code :

``` boolean setNumberMeAndTheRest(Board board) {   if(next == null) { for(int i = 1; i < board.getDimension(); i++) { if(legalValue(i)) { setValue(i); } } board.saveSolution(); System.out.println("Saved a solution"); return true; }   if(this instanceof DefinedSquare) { return next.setNumberMeAndTheRest(board); }   for(int i = 1; i <= board.getDimension(); ++i) { if(legalValue(i)) { setValue(i);   if(next.setNumberMeAndTheRest(board)) { return true; } } } setValue(0); return false; }```

I need help with two thing:

1. Make the algorithm to work for all dimension/ type of sudoko boards.
2. Save all possible solutions for a board, or will this happen automatically when the algorithm works right, i saves a board "board.saveSolution();" when the algorithm finds the last value in the last square.

Appreciate the help