Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Java Sudoku Project (Using Human Techniques)

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
Moorst

Joined: 24 Nov 2008
Posts: 6
:

Items
PostPosted: Mon Nov 24, 2008 4:52 pm    Post subject: Java Sudoku Project (Using Human Techniques) Reply with quote
Hey there, I'm currently trying to create a Sudoku solver, and I'm having some problems getting my head around a few things. I'm a Java newbie really, but I'm very interested in it, and I'm certainly trying my best!

At the moment I've created my data structure, and I'm concentrating on trying to check the rows, columns and boxes for numbers and finding out the possibilities for each empty cell. This can then lead onto implementing algorithms such as Naked Pairs, Subsets etc.

If you guys could help me get started it would be much appreciated, I know these types of things come so easily to you guys, but I'm really having trouble with it!

Code:
public class Moodoku
{
   //-------------------Declarations-------------------\\
   public static int gridSize = 9;                                  //Number of Rows and Columns
   public static int subgridSize = 3;                              //SubGrid size               
    public int[][] grid = grid1;                                  //Sudoku Grid (new int[gridSize][gridSize] for empty grid)
   public static int defaultNumber = 0;                              //Default/No Value
    public int row, column, number;                                 //Public integers
     
    //-------------------Enter Sudoku Grid (9x9)-------------------\\   
    static int[][] grid1 =
    {
        {0, 0, 0, 0, 8, 0, 0, 1, 6},
        {0, 6, 3, 0, 0, 1, 4, 0, 2},
        {1, 9, 0, 0, 0, 6, 0, 0, 0},
        {2, 0, 0, 8, 0, 5, 6, 9, 0},         //'0' is default number, which will be processed as empty cell
        {6, 7, 0, 0, 0, 0, 0, 2, 5},
        {0, 4, 9, 6, 0, 3, 0, 0, 8},
        {0, 0, 0, 2, 0, 0, 0, 8, 3},
        {3, 0, 5, 9, 0, 0, 2, 4, 0},
        {7, 2, 0, 0, 3, 0, 0, 0, 0},
    };
   
    //-------------------Main-------------------\\
    public static void main(String[] args)
    {
       new Moodoku();
       
    }
   
    //-------------------Call printGrid(), non static context-------------------\\   
    public Moodoku()
    {
       printGrid();
    }
       
    //-------------------Create Empty Grid-------------------\\
    /*public void Grid()
    {       
       for (row = 0; row < gridSize; row++)
       {
           for (column = 0; column < gridSize; column++)
           {
                grid[row][column] = defaultValue;
           }
       }
    }*/
   
    //-------------------Retrieve Number From Sudoku Grid-------------------\\
    public int retrieveNumber(int row, int column)
    {   
        return grid[row][column];
    }
   
    //-------------------Set Retrieved Number as 'number'-------------------\\   
    public void setNumber(int row, int column, int number)
    {
          this.grid[row][column] = number;
    }
   
    //-------------------Print the Grid-------------------\\
    public void printGrid()
    {
       for (row = 0; row < gridSize; row++)
          {
             if (row % subgridSize == 0) System.out.println(" -----------------------");      //Print line after every 3 rows for subgrid
             
             for (column = 0; column < gridSize; column++)
            {
               if (column % subgridSize == 0) System.out.print("| ");                   //Print '|' after every 3 columns for subgrid
               
                number = retrieveNumber(row, column);
               
                if (number == defaultNumber)
                {
                    System.out.print("_ ");               //If number retrieved is 0, cell is not filled
                }
                else
                {
                    System.out.print(number + " ");        //Else, print the number retrieved
                }
            }
           
            System.out.println("|");
           
         }
         
         System.out.println(" -----------------------");
    }
}


As you can see my code is not very advanced, this is how I've set it up. At the moment I've got the grid to print, identifying the 0's as empty cells.

I'm now trying to implement the checkRow and checkColumn methods, as shown below

Code:
//-------------------Check the Rows-------------------\\
    public static boolean checkRow(int n, int row, int start, int limit)
    {
        for (int i = start; i < limit; i++)
        {

            if (grid1[row][i] == n) return true;
        }
       
        return false;
    }
   
    //-------------------Check if a number is present in a Row-------------------\\
    public static boolean checkRow(int n, int row)
    {
        return checkRow(n, row, 0, grid1.length);
    }
   
    //-------------------Check the Columns-------------------\\
    public static boolean checkCol(int n, int column, int start, int limit)
    {
        for (int i = start; i< limit; i++)
        {
            if (grid1[i][column] == n) return true;
        }
       
        return false;
    }   

    //-------------------Check if a number is present in a Column-------------------\\
    public static boolean checkCol(int n, int column) {
        return checkCol(n, column, 0, grid1.length);
    }


I'm now uncertain how I can create such a method for the 3x3 boxes, and how ultimately I can compare them all to try and solve a given puzzle.

My idea would be to store 9 numbers in each cell, and search through the whole grid and remove the numbers that are not a possibility for that cell, because of corresponding numbers being housed in the same row/column/box. Despite this, I'm having trouble putting my idea into code surprisingly!

If anyone can guide me in the right direction I'd greatly appreciate it, any advice will be taken on board!

Is there any better way for me to structure the whole thing?

How can I identify 3x3 boxes and compare the rows, column and boxes?

I assume I need a way to store possible numbers for each cell, and a method to remove numbers that aren't possible, what is the best way to do this?

Thank you in advance, if anything is unclear please notify me.

x

[/code]
Back to top
View user's profile Send private message
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Mon Nov 24, 2008 6:05 pm    Post subject: Reply with quote
Hey Moorst - welcome to the forum.

I know *zip* about Java and using OOP, but I keep an array of possibles for each cell on the grid.

And I do indeed delete those digits, as they become impossible. I like to display them also, if the program is just solving one puzzle, and it's not a speed contest.

I use two nested for loops to check on the 3X3 boxes. Before that, I use a series of if statements that are designed to look at the square number (array element #), and determine what is the right low row, and low column, for that square. A table look up would be much faster, but that's for version 2. Wink

The code is not short, nor elegant really. It does run fine (acceptably fast), until it gets to the brute force function (should it be unsolved otherwise by the human type logic functions).

Oddly, the brute force solver has the most optimized code in my program, but it's stuck in a slow overall algorithm - so it's barely tolerable for speed.

Good luck with your program.
Back to top
View user's profile Send private message
Pete

Joined: 09 Jun 2008
Posts: 18
:
Location: Somerset, NJ

Items
PostPosted: Mon Nov 24, 2008 11:52 pm    Post subject: Reply with quote
Welcome aboard!

There are several ways to approach this. My program is also written in Java. Here's what I did.

I created a Puzzle class to hold all of the cells. Each puzzle also holds a collection of its houses. House is another class that represents a row, column, or block. This lets me treat each house the same (i.e., The same code is used to find singles in a row, column, or block).

Then there is a Cell class. Each cell keeps track of its state (given, solved, or unsolved), as well as its candidates. My first draft used an array of booleans to tell whether each possible value was a candidate. The current version does this using a bit set.

If you'd like to take a look at my source code, it's available on SourceForge under the name Dancing Links Sudoku.

I hope this helps. Good luck with it! Please let us know when you have it working.

Pete
Back to top
View user's profile Send private message AIM Address
Moorst

Joined: 24 Nov 2008
Posts: 6
:

Items
PostPosted: Wed Nov 26, 2008 1:15 am    Post subject: Reply with quote
Thanks for the tips guys, really appreciated.

At the moment I've managed to create methods to check columns, rows, and pretty much a method similar to the printGrid one i posted in the first place, to check all the cells. With this, I'm trying to create an ArrayList (the path I've chosen!) for every cell, knocking out values that are in the filled cells just for a start. How would I go about storing a new ArrayList for every cell?

I've tried using an ArrayList for checking a row or column, and at the moment it's knocking the completely wrong numbers out for some reason and I cannot understand why:

Code:
public void checkColumn()
    {
       for (int column = 0; column < gridSize; column++)
        {
           number = retrieveNumber(row, column);
            if (poss.contains(number))
            {
               poss.remove(number); 
               System.out.println("Removed " + number + " as possible entry for Column: " + columnNumber) ;
               columnNumber++;            
            }
           
            else
            {
               columnNumber++;
            }
        }
       
    }


I know that this code isn't going to work in the end product for my method of checking every cell, but I'm just trying to grasp a few things regarding the ArrayLists. While using the code above for the row:

{0, 0, 0, 0, 8, 0, 0, 1, 6}

of a sudoku grid, it says that the remaining values of my ArrayList (containing 1 - 9) are:

Possibilities: [1, 3, 4, 5, 6, 7].

I cannot understand this, and that is why I have included a println, which tells me that the right numbers are being removed (8, 1, 6, leaving 234579)

Am I using the ArrayLists in the completely wrong way?

If I manage to get the ArrayList to knock out the right numbers, what would eb the best way to create a new one for every cell, and store the possible numbers for that particular cell?

Thanks for the help guys, I apologise that I require so much help!

x
Back to top
View user's profile Send private message
hobiwan

Joined: 11 Feb 2008
Posts: 83
:

Items
PostPosted: Thu Nov 27, 2008 7:01 pm    Post subject: Reply with quote
Moorst wrote:
Am I using the ArrayLists in the completely wrong way?

ArrayList has two methods remove():

E remove(int index)

and

boolean remove(Object o)

That means: If you call poss.remove(number) you remove the number at index "number" instead of the value of number itself. I didn't try it but I think even if you use Generics and declare your List as ArrayList<Integer> you had to call

poss.remove(new Integer(number))

to make it work.
Back to top
View user's profile Send private message
Moorst

Joined: 24 Nov 2008
Posts: 6
:

Items
PostPosted: Thu Nov 27, 2008 8:21 pm    Post subject: Reply with quote
Thank you mate! Works fine now, just need to work out a way to create arraylists for every cell of the grid now.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron