Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 6 of 6

Thread: Brute force Sudoku algorithm is not working

  1. #1
    Junior Member
    Join Date
    Apr 2012
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

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


  2. #2
    Super Moderator pbrockway2's Avatar
    Join Date
    Jan 2012
    Posts
    987
    Thanks
    6
    Thanked 206 Times in 182 Posts

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

    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.

    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);
        }
    }
    Last edited by pbrockway2; April 18th, 2012 at 06:49 PM.

  3. #3
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,676
    Thanks
    25
    Thanked 329 Times in 305 Posts

    Default 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.
    NOTE TO NEW PEOPLE LOOKING FOR HELP ON FORUM:

    When asking for help, please follow these guidelines to receive better and more prompt help:
    1. Put your code in Java Tags. To do this, put [highlight=java] before your code and [/highlight] after your code.
    2. Give full details of errors and provide us with as much information about the situation as possible.
    3. Give us an example of what the output should look like when done correctly.

    Join the Airline Management Simulation Game to manage your own airline against other users in a virtual recreation of the United States Airline Industry. For more details, visit: http://airlinegame.orgfree.com/

  4. #4
    Junior Member
    Join Date
    Apr 2012
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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.

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

  5. #5
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,676
    Thanks
    25
    Thanked 329 Times in 305 Posts

    Default Re: Brute force Sudoku algorithm is not working

    How confident are you that the legalValue(int value) method is working correctly?
    NOTE TO NEW PEOPLE LOOKING FOR HELP ON FORUM:

    When asking for help, please follow these guidelines to receive better and more prompt help:
    1. Put your code in Java Tags. To do this, put [highlight=java] before your code and [/highlight] after your code.
    2. Give full details of errors and provide us with as much information about the situation as possible.
    3. Give us an example of what the output should look like when done correctly.

    Join the Airline Management Simulation Game to manage your own airline against other users in a virtual recreation of the United States Airline Industry. For more details, visit: http://airlinegame.orgfree.com/

  6. #6
    Junior Member
    Join Date
    Apr 2012
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Brute force Sudoku algorithm is not working

    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

Similar Threads

  1. Password Hash - Brute Force Test - SHA-1
    By djl1990 in forum What's Wrong With My Code?
    Replies: 5
    Last Post: February 14th, 2012, 03:36 PM
  2. Finding Chromatic Number w/ Brute Force Algorithm
    By thecrazytaco in forum Algorithms & Recursion
    Replies: 2
    Last Post: November 16th, 2011, 07:35 AM
  3. Finding Chromatic Number of a Simple Graph w/ Brute Force Algorithm
    By thecrazytaco in forum What's Wrong With My Code?
    Replies: 3
    Last Post: November 15th, 2011, 09:27 PM
  4. sudoku using graph coloring algorithm
    By priyank in forum Algorithms & Recursion
    Replies: 3
    Last Post: April 21st, 2011, 02:22 PM
  5. Problem with Brute Force
    By mortis1572 in forum File I/O & Other I/O Streams
    Replies: 0
    Last Post: March 14th, 2010, 09:52 AM

Tags for this Thread