Thread: 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

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;
	}
}

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.

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;
	}

I´m pretty sure that legalValue(int value) works, under is the code for the function:

	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

	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