Your Ad Here

Friday, April 10, 2009

Sudoku Solver using sets

A friend and I are trying to create a very basic Sudoku Solver using sets. This is what we have come up with and it works but there has to be a way to simplify. Is there anyone out there that can give us some suggestions on how to simplify?

[code]
import java.util.*;

public class Solver
{
public Solver(int [][] game)
{
cellSolved = 0;
cells = new int [SIZE][SIZE];
{
possibles = (Set[][]) new Set[SIZE][SIZE];
{
for(int i = 0; i< SIZE; i++)
{
for(int j = 0; j < SIZE; j++)
{
possibles[i][j] = new TreeSet();
}
}
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 for(int c = 0; 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 possibles[row][c].remove(n);
}
private void removeFromSetsCol(int n, int col)
{
for(int r =0; 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 for(int c = startCol; 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[][] possibles;
private int [][]cells;
}
[end code]

This is the tester:
[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 {
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");



}
}

}
[end code]

Read More...
Your Ad Here

No comments: