Sudoku Solver Using sets

Create a Sudoku Sover using Sets

Page 1 of 1

6 Replies - 2257 Views - Last Post: 10 April 2009 - 07:57 AM Rate Topic: -----

#1 nanoo51969  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 23-March 09

Sudoku Solver Using sets

Post icon  Posted 08 April 2009 - 08:37 PM

A friend and I are working on a Sudoku Solver that uses sets.
We have a version that works but was wondering if there is anything we can do to simplify this a bit. The idea is to use the sets. Can anyone help?


import java.util.*;

public class Solver 
{
	public Solver(int [][] game)
	{
		cellSolved = 0;
		cells = new int [SIZE][SIZE];
		{
		possibles = (Set<Integer>[][]) new Set[SIZE][SIZE];
		 {		
			for(int i = 0; i< SIZE; i++)
			{
				for(int j = 0; j < SIZE; j++)
				{				  
					possibles[i][j] = new TreeSet<Integer>();
				}
			}				
				 for(int i = 0; i < SIZE; i++)
				 {
					 for(int j = 0; j< SIZE; j++)
					{
					 cells[i][j] = 0;
					 for(int k = 1; k < SIZE; k++)
						possibles[i][j].add(k);
					}			   
				 }
		 }	
	int n;
		for(int r = 0; r<SIZE; r++)
			for(int c = 0; c<SIZE; c++)
			{
				n = game[r][c];
					if(n !=0)
					{
						possibles[r][c].clear();
						cellSolved++;
					}
				add(n, r, c);
			}
		}
	}	
	private void add(int n, int row, int col)
		{
		cells[row][col] = n;
		removeFromSetsRow(n,row);
		removeFromSetsCol(n,col);
		removeFromSetsBlock(n,row,col);
		}	
	private void removeFromSetsRow(int n, int row)
		{
		for(int c = 0; c<SIZE; c++)
			possibles[row][c].remove(n);
		}	
	private void removeFromSetsCol(int n, int col)
		{
		for(int r =0; r<SIZE; r++)
			possibles[r][col].remove(n);		
		}	
	private void removeFromSetsBlock(int n, int row, int col)
		{
		int startRow = (row/3)*3;
		int startCol = (col/3)*3;
		for(int r = startRow; r<startRow + 3; r++)
			for(int c = startCol; c<startCol + 3; c++)
				possibles[r][c].remove(n);
		}	
	public void Solve()
		{
		boolean done = false;
		int r,c,n;
		
		while(!done)
			{
			done = true;
			for(r = 0; r< SIZE; r++)
				for(c = 0; c< SIZE; c++)
				{
					if(possibles[r][c].size()==1);
					{
						done = false;
						n = possibles[r][c].iterator().next();
						add(n,r,c);
						cellSolved++;
					}	   
				}
			}
		}	
	public boolean isSolved()
	{
		return cellSolved = SIZE * SIZE;
	}  
	public static final int SIZE = 9;
	private int cellSolved;
	private Set<Integer>[][] possibles;
	private int [][]cells;
}
[code/]

[quote]
this is the tester
[quote/]

[code]
import java.io.*;
import java.util.Scanner;


public class Tester 
{

	/**
	 * @param args the command line arguments
	 */
	public static void main(String[] args)
			throws FileNotFoundException
	{
		Scanner myScanner = new Scanner(System.in);
		System.out.print("Enter name of input file: ");
		String inputFileName = myScanner.next();
		
		FileReader reader = new FileReader(inputFileName);
		Scanner in = new Scanner(reader);
  
		int[][]game = new int[Solver.SIZE][Solver.SIZE];
			for(int r = 0; r<Solver.SIZE; r++)
				{
				for(int c = 0; c < Solver.SIZE;)
					game[r][c] = in.nextInt();
				}
		in.close();
		Solver sud = new Solver(game);
		System.out.println("Here is original game");
		System.out.println(sud);
		sud.Solve();
		
		if(sud.isSolved())
			{
			System.out.println("Game solved, see solution");
			System.out.println(sud);
			}
		else
			{
			System.out.print("Game not solved");
			System.out.println("This is as far as I got");
			System.out.println(sud);
			System.out.print("Possible sets");
			System.out.println("When program terminated");
		}
	}

}



Can this be simplified using sets?
[/quote]

*Edited to correct the [ /code] tag

This post has been edited by pbl: 09 April 2009 - 07:28 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Sudoku Solver Using sets

#2 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8334
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: Sudoku Solver Using sets

Posted 08 April 2009 - 08:47 PM

Your code is a pain to read
Please respect rule #4 of this forum that says :code:
This rule was displayed to you when you posted your code

Go back and edit your ost and add the correct [ code][ /code] tags

This post has been edited by pbl: 08 April 2009 - 08:48 PM

Was This Post Helpful? 0
  • +
  • -

#3 nanoo51969  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 23-March 09

Re: Sudoku Solver Using sets

Posted 08 April 2009 - 09:12 PM

View Postpbl, on 8 Apr, 2009 - 07:47 PM, said:

Your code is a pain to read
Please respect rule #4 of this forum that says :code:
This rule was displayed to you when you posted your code

Go back and edit your ost and add the correct [ code][ /code] tags

This post has been edited by nanoo51969: 08 April 2009 - 09:40 PM

Was This Post Helpful? 0
  • +
  • -

#4 Fuzzyness  Icon User is offline

  • Comp Sci Student
  • member icon

Reputation: 669
  • View blog
  • Posts: 2,438
  • Joined: 06-March 09

Re: Sudoku Solver Using sets

Posted 08 April 2009 - 09:17 PM

oooooo my gosh duuuuude, you must be more stoned then I am.

:code:

Pl0x and Thanks x . x
Was This Post Helpful? 0
  • +
  • -

#5 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8334
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: Sudoku Solver Using sets

Posted 09 April 2009 - 07:30 PM

What do you really mean by "set" and how do you plan to implement them ?
Was This Post Helpful? 0
  • +
  • -

#6 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5833
  • View blog
  • Posts: 12,689
  • Joined: 16-October 07

Re: Sudoku Solver Using sets

Posted 10 April 2009 - 07:36 AM

Damn, that's some confusing code. :P

And not without bugs. You have brackets where you don't need them, there are places where I wish you had them. While I try not to be judgmental of other people's coding style, putting the variable declarations for a class at the bottom hurts.

bugs
public boolean isSolved() {
	// oops
	//return cellSolved = SIZE * SIZE;
	return cellSolved == (SIZE * SIZE);
}  

Solver sud = new Solver(game);
System.out.println("Here is original game");
// the toString of Solver is never implemented.
// what should I expect to see?
System.out.println(sud);



Things that would make this easier would be having Board and Cell classes. Mostly because "int [SIZE][SIZE]" doesn't jump out and say sudoku board. Also, because if you could lay you possibles in your cell bucket, it would be more logically obvious to follow.

e.g.
class Cell {
	public static final int EMPTY_CELL = 0;
	public Cell() { /* your code here */ }
	public Cell(int value) { /* your code here */ }
	public void setValue(int value) { /* your code here */ }
	public boolean isEmpty() { /* your code here */ }
	public boolean isPossible(int value) { /* your code here */ }
	public void removePossible(int value) { /* your code here */ }
	public int getPossibleCount() { /* your code here */ }
	public boolean isValid() { return (!isEmpty() || getPossibleCount()!=0); }
}

class Board {
	public void init(int [][] a) { /* your code here */ }
	public void init(int [] a) { /* your code here */ }
	public void init(String s) { /* your code here */ }
	public void setValue(int row, int col, int value) { /* your code here */ }
	public int getValue(int row, int col) { /* your code here */ }
	public Cell getCellValue(int row, int col) { /* your code here */ }
	public Cell getCellValue(int row, int col) { /* your code here */ }
	public boolean isValid() { /* your code here */ }
	public boolean isSolved() { /* your code here */ }
}



I might actually try that design, looks like fun. I did sudoku solver in snippets, but it's C and uses bits and is probably a little cryptic itself.

The only thing a set would buy you is a way to do isPossible, removePossible, and getPossibleCount on a cell. How you do that is up to you. Clarity of code is preferred to implementation details. If the basics are easy to follow, the complex stuff is easier to put in behind it. Viva la OOP.

Hope this helps.
Was This Post Helpful? 0
  • +
  • -

#7 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8334
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: Sudoku Solver Using sets

Posted 10 April 2009 - 07:57 AM

View Postbaavgai, on 10 Apr, 2009 - 06:36 AM, said:

Damn, that's some confusing code. :P

And not without bugs. You have brackets where you don't need them, there are places where I wish you had them. While I try not to be judgmental of other people's coding style, putting the variable declarations for a class at the bottom hurts.

I thing that too: "putting the variable declarations for a class at the bottom hurts"

But this is what Horstmann and Cornell did in all their "Core Java" manuals published by Sun.

Volume 1 - Fundamentals Page: 131

"We adopt the style that the methods for the class come first and the fields come at the end. Perhaps this, in a small way, encourages the notion of looking at the interface first and paying less attention to the implementation"

With all the respects I have for these 2 folks, I agree with you Baavgai but we can see why people might use this convention.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1