Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
HomeAnnouncementsWhite Papers
Discussion GroupsFirst AidDatabasesJavaBeansGUIJava 3DVirtual MachineCORBASecurityToolsGeneral
Java DirectoryOpen Source ProjectsSample Book ChaptersUser GroupsWeb Resources
Related Topics
Databases.NETMore Topics ...

Java Forum / First Aid / December 2005

Tip: Looking for answers? Try searching our database.

Suduko solver demo

Thread view: 
bherbst65@hotmail.com - 27 Dec 2005 17:08 GMT
Hi All,

I am looking for a link to help write a suduko puzzle solver, an
application type. I have seen
applets that the user enters the data, the solution help is given,  but
it is also web based.

I have been unable to find any applications.

TIA

Bob
Rhino - 27 Dec 2005 19:10 GMT
> Hi All,
>
[quoted text clipped - 4 lines]
>
> I have been unable to find any applications.

Your question is confusing.

Are you looking for Sudoku solver that is already completely written and
working but that may not include source code? Are you looking for all of the
Java source code needed to solve Sudokus? Or do you want help to write your
own solution?

If you are looking for a working Sudoku solver, what platform are you using?
I found a good solver for my Palm PDA and I think it is written in Java but
I don't think you can get source code for it: would that meet your
requirements?

Rhino
bherbst65@hotmail.com - 27 Dec 2005 23:02 GMT
Hi Rhino,

To clarify,  I am looking for help that will allow me write my own
solution.

Hopefully  it will be an application program run on my computer
usingWin2K with NT. In my searching I have looked at  some persons
that have shared the applet source code but these use import resources
that are beyond the java download  jdk1.5.0_05 which I have.

Bob
Andrew Thompson - 27 Dec 2005 23:30 GMT
> To clarify,  I am looking for help that will allow me write my own
> solution.

So take the code for the applet you mentioned earlier,
and convert it into an application.

Do you know how to convert an applet to an application?

Signature

Andrew Thompson
physci, javasaver, 1point1c, lensescapes - athompson.info/andrew

bherbst65@hotmail.com - 28 Dec 2005 15:43 GMT
Hi Andrew,
I am trying to do what you suggested above.
This is an ?applet?  form of the sudoku solver as downloaded. It
doesn't look that way to me. So I compiled it,  and the errors are
noted below the data.
Can you or someone else please explain what it is or what this further
needs?

This is very confusing.

/* Copyright 2005 Ilkka Kokkarinen.
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
* GNU General Public License for more details.

* @author Ilkka Kokkarinen
* @version 0.01
*/

import java.util.*;

public class Sudoku {

   private Cell[][] squareContents;
   private List remainingCells;
   private int lastSort;

   /* Used to sort the cells in order of remaining possibilities. */
   private class CellComparator implements Comparator {
       public int compare(Object o1, Object o2) {
           Cell c1 = (Cell)o1;
           Cell c2 = (Cell)o2;
           return c2.digitRuledOutCount - c1.digitRuledOutCount;
       }
   }
   private CellComparator comp = new CellComparator();

   /* Information about a single cell. */
   public class Cell {
       private int x;
       private int y;
       public int inSquare;
       public int[] digitRuledOut;
       public int digitRuledOutCount;
       public int value;

       public Cell(int x, int y) {
           this.x = x;
           this.y = y;
           this.inSquare = 3 * (x / 3) + (y / 3);
           this.digitRuledOutCount = 9;
           this.digitRuledOut = new int[10];
           this.value = 0;
       }

       /* Rules out digit v in this cell. */
       private boolean ruleOutDigit(int v, int depth) {
           if(value == 0 && digitRuledOut[v] == 0) {
               digitRuledOut[v] = depth;
               if(--digitRuledOutCount == 0) { return true; }
           }
           return false;
       }

       /* Rules in digit v in this cell. */
       private void ruleInDigit(int v, int depth) {
           if(digitRuledOut[v] == depth) {
               digitRuledOut[v] = 0;
               digitRuledOutCount++;
           }
       }

       /* Sets the value of this cell and rules it out in other cells.
*/
       public boolean setValue(int value, int depth) {
           this.value = value;
           for(int i = 0; i < 9; i++) {
               if(board[x][i].ruleOutDigit(value, depth)) return true;
               if(board[i][y].ruleOutDigit(value, depth)) return true;
               if(squareContents[inSquare][i].ruleOutDigit(value,
depth)) return true;
           }
           return false;
       }

       /* Erases the value of this cell, ruling it in in other cells.
*/
       public void eraseValue(int depth) {
           for(int i = 0; i < 9; i++) {
               board[x][i].ruleInDigit(value, depth);
               board[i][y].ruleInDigit(value, depth);
               squareContents[inSquare][i].ruleInDigit(value, depth);
           }
           this.value = 0;
       }
   }

   public Cell[][] board;

   /* Initialize the solver. */
   public boolean solve(int[][] initBoard) {
       board = new Cell[9][9];
       remainingCells = new ArrayList();
       squareContents = new Cell[9][9];
       int[] squareCount = new int[9];

       for(int x = 0; x < 9; x++) {
           for(int y = 0; y < 9; y++) {
               Cell c = new Cell(x,y);
               board[x][y] = c;
               squareContents[c.inSquare][squareCount[c.inSquare]++] =
board[x][y];
           }
       }

       for(int x = 0; x < 9; x++) {
           for(int y = 0; y < 9; y++) {
               if(initBoard[x][y] > 0) {
                   board[x][y].setValue(initBoard[x][y], 100);
               }
               else {
                   remainingCells.add(board[x][y]);
               }
           }
       }
       Collections.sort(remainingCells, comp);
       return backtrack(1);
   }

   /* The backtracking search algorithm. */
   public boolean backtrack(int depth) {
       if(remainingCells.isEmpty()) { return true; }
       if(depth == lastSort + 5 || depth == lastSort - 5) {
           Collections.sort(remainingCells, comp);
           lastSort = depth;
       }
       Cell current =
(Cell)remainingCells.remove(remainingCells.size()-1);

       for(int v = 1; v <= 9; v++) {
           if(current.digitRuledOut[v] != 0) continue;
           if(current.setValue(v, depth)) {
               current.eraseValue(depth);
           }
           else {
               if(backtrack(depth + 1)) return true;
               current.eraseValue(depth);
           }
       }

       remainingCells.add(current);
       return false;
   }

   /* A few test boards. */
   public void test() {
       int[][] testBoard = {
           {0,6,0,1,0,4,0,5,0},
           {0,0,8,3,0,5,6,0,0},
           {2,0,0,0,0,0,0,0,1},

           {8,0,0,4,0,7,0,0,6},
           {0,0,6,0,0,0,3,0,0},
           {7,0,0,9,0,1,0,0,4},

           {5,0,0,0,0,0,0,0,2},
           {0,0,7,2,0,6,9,0,0},
           {0,4,0,5,0,8,0,7,0}
       };

       solve(testBoard);
   }

   public void test2() {
       int[][] testBoard = {
           {0,0,0,0,0,0,0,3,8},
           {0,2,3,4,0,8,0,0,0},
           {0,8,0,5,2,0,1,0,9},

           {0,0,0,6,7,4,0,5,0},
           {0,0,0,0,0,0,0,0,0},
           {0,1,0,3,5,9,0,0,0},

           {1,0,5,0,4,7,0,9,0},
           {0,0,0,9,0,2,7,1,0},
           {2,9,0,0,0,0,0,0,0}
       };

       solve(testBoard);
   }

}

8 warnings found:
File: C:\Documents and Settings\R Herbst\Desktop\Sudoku
Solver\Sudoku.java  [line: 114]
Warning: [unchecked] unchecked call to add(E) as a member of the raw
type java.util.List
File: C:\Documents and Settings\R Herbst\Desktop\Sudoku
Solver\Sudoku.java  [line: 118]
Warning: [unchecked] unchecked method invocation:
<T>sort(java.util.List<T>,java.util.Comparator<? super T>) in
java.util.Collections is applied to
(java.util.List,Sudoku.CellComparator)
File: C:\Documents and Settings\R Herbst\Desktop\Sudoku
Solver\Sudoku.java  [line: 118]
Warning: [unchecked] unchecked conversion
found   : java.util.List
required: java.util.List<T>
File: C:\Documents and Settings\R Herbst\Desktop\Sudoku
Solver\Sudoku.java  [line: 118]
Warning: [unchecked] unchecked conversion
found   : Sudoku.CellComparator
required: java.util.Comparator<? super T>
File: C:\Documents and Settings\R Herbst\Desktop\Sudoku
Solver\Sudoku.java  [line: 126]
Warning: [unchecked] unchecked method invocation:
<T>sort(java.util.List<T>,java.util.Comparator<? super T>) in
java.util.Collections is applied to
(java.util.List,Sudoku.CellComparator)
File: C:\Documents and Settings\R Herbst\Desktop\Sudoku
Solver\Sudoku.java  [line: 126]
Warning: [unchecked] unchecked conversion
found   : java.util.List
required: java.util.List<T>
File: C:\Documents and Settings\R Herbst\Desktop\Sudoku
Solver\Sudoku.java  [line: 126]
Warning: [unchecked] unchecked conversion
found   : Sudoku.CellComparator
required: java.util.Comparator<? super T>
File: C:\Documents and Settings\R Herbst\Desktop\Sudoku
Solver\Sudoku.java  [line: 142]
Warning: [unchecked] unchecked call to add(E) as a member of the raw
type java.util.List
Rhino - 28 Dec 2005 16:31 GMT
The messages from the compiler are not errors, they are warnings. That means
that your .class file should have been generated and the program should run.
The program _might_ misbehave but it is quite possible that it will run
satisfactorily. I would suggest you try running it just the way it is and
see if it works: it's very possible that you won't have a problem.

Now, there are a few strategies to take with respect to your warnings:
1. Ignore them. This is the easiest thing but it probably isn't very
satisfying; if you're like me,  you don't want _any_ errors or warnings in
your programs. Also, you are left with the fear that the program will break
at runtime and it may be difficult to solve the problem.
2. Disable warnings of this type in your compiler so that those conditions
don't produce warning messages. You can almost certainly tell your compiler
to simply ignore certain types of conditions, like these and then no
messages will be produced. In your case, all of the messages seem to involve
generics in some way; generics are new to Java 1.5. The consequences of
disabling these messages are similar to those for the previous strategy.
3. Revise the code so that there is nothing for the compiler to complain
about. This will be a bit more work but will get rid of the messages so that
you don't need to worry about them biting you at runtime. To resolve these
errors, look at the documentation in the Java 1.5 API, which you probably
have on your computer somewhere. You can also find them here:
http://java.sun.com/j2se/1.5.0/docs/relnotes/features.html. Click on the
items in the "Java Language Features" section, particularly "Generics" and
you will probably see what you need to do to make the warnings go away.

Rhino

> Hi Andrew,
> I am trying to do what you suggested above.
[quoted text clipped - 236 lines]
> Warning: [unchecked] unchecked call to add(E) as a member of the raw
> type java.util.List
Patrick May - 28 Dec 2005 16:38 GMT
> I am trying to do what you suggested above.  This is an ?applet?
> form of the sudoku solver as downloaded. It doesn't look that way to
> me. So I compiled it, and the errors are noted below the data.
>
> Can you or someone else please explain what it is or what this
> further needs?

    The warnings you saw were due to your use of a version 1.5
compatible compiler.  They can be eliminated through the use of
generics.  I've provided a modified version below that compiles
without warnings.

    I've also added a main() method that calls the two test methods.
If you want to see output, you'll have to add some code to print the
solved puzzles.

Regards,

Patrick

------------------------------------------------------------------------
S P Engineering, Inc.    | The experts in large scale distributed OO
                        | systems design and implementation.
         pjm@spe.com    | (C++, Java, Common Lisp, Jini, CORBA, UML)

/* Copyright 2005 Ilkka Kokkarinen.
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
* GNU General Public License for more details.

* @author Ilkka Kokkarinen
* @version 0.01
*/

import java.util.*;

public class Sudoku
{
 private Cell[][] squareContents;
 private ArrayList<Cell> remainingCells = new ArrayList<Cell>();
 private int lastSort;

 // Used to sort the cells in order of remaining possibilities.
 private class CellComparator implements Comparator<Cell>
   {
   public int compare(Cell cell1,Cell cell2)
     {
     return cell2.digitRuledOutCount - cell1.digitRuledOutCount;
     }
   }

 private CellComparator comp = new CellComparator();

 // Information about a single cell.
 public class Cell
   {
   private int x;
   private int y;
   public int inSquare;
   public int[] digitRuledOut;
   public int digitRuledOutCount;
   public int value;

   public Cell(int x,int y)
     {
     this.x = x;
     this.y = y;
     this.inSquare = 3 * (x / 3) + (y / 3);
     this.digitRuledOutCount = 9;
     this.digitRuledOut = new int[10];
     this.value = 0;
     }

   // Rules out digit v in this cell.
   private boolean ruleOutDigit(int v,int depth)
     {
     if (value == 0 && digitRuledOut[v] == 0)
       {
       digitRuledOut[v] = depth;
       if (--digitRuledOutCount == 0)
         return true;
       }

     return false;
     }

     // Rules in digit v in this cell.
   private void ruleInDigit(int v,int depth)
     {
     if (digitRuledOut[v] == depth)
       {
       digitRuledOut[v] = 0;
       digitRuledOutCount++;
       }
     }

   // Sets the value of this cell and rules it out in other cells.
   public boolean setValue(int value,int depth)
     {
     this.value = value;
     for(int i = 0; i < 9; i++)
       {
       if (board[x][i].ruleOutDigit(value,depth))
         return true;
       if (board[i][y].ruleOutDigit(value,depth))
         return true;
       if (squareContents[inSquare][i].ruleOutDigit(value,depth))
         return true;
       }
     return false;
     }

   // Erases the value of this cell, ruling it in in other cells.
   public void eraseValue(int depth)
     {
     for(int i = 0; i < 9; i++)
       {
       board[x][i].ruleInDigit(value,depth);
       board[i][y].ruleInDigit(value,depth);
       squareContents[inSquare][i].ruleInDigit(value,depth);
       }

     this.value = 0;
     }
   }

 public Cell[][] board;

 // Initialize the solver.
 public boolean solve(int[][] initBoard)
   {
   board = new Cell[9][9];
   squareContents = new Cell[9][9];
   int[] squareCount = new int[9];

   for(int x = 0; x < 9; x++)
     for(int y = 0; y < 9; y++)
       {
       Cell c = new Cell(x,y);
       board[x][y] = c;
       squareContents[c.inSquare][squareCount[c.inSquare]++] =
         board[x][y];
       }

   for(int x = 0; x < 9; x++)
     for(int y = 0; y < 9; y++)
       if (initBoard[x][y] > 0)
         board[x][y].setValue(initBoard[x][y],100);
       else
         remainingCells.add(board[x][y]);

   Collections.sort(remainingCells,comp);
   return backtrack(1);
   }

 // The backtracking search algorithm.
 public boolean backtrack(int depth)
   {
   if (remainingCells.isEmpty())
     return true;

   if (depth == lastSort + 5 || depth == lastSort - 5)
     {
     Collections.sort(remainingCells,comp);
     lastSort = depth;
     }
   Cell current = (Cell)remainingCells.remove(remainingCells.size()-1);

   for(int v = 1; v <= 9; v++)
     {
     if (current.digitRuledOut[v] != 0)
       continue;

     if (current.setValue(v,depth))
       current.eraseValue(depth);
     else
       {
       if (backtrack(depth + 1))
         return true;

       current.eraseValue(depth);
       }
     }

   remainingCells.add(current);
   return false;
   }

 // A few test boards.
 public void test()
   {
   int[][] testBoard = { {0,6,0,1,0,4,0,5,0},
                         {0,0,8,3,0,5,6,0,0},
                         {2,0,0,0,0,0,0,0,1},

                         {8,0,0,4,0,7,0,0,6},
                         {0,0,6,0,0,0,3,0,0},
                         {7,0,0,9,0,1,0,0,4},

                         {5,0,0,0,0,0,0,0,2},
                         {0,0,7,2,0,6,9,0,0},
                         {0,4,0,5,0,8,0,7,0} };

   solve(testBoard);
   }

 public void test2()
   {
   int[][] testBoard = { {0,0,0,0,0,0,0,3,8},
                         {0,2,3,4,0,8,0,0,0},
                         {0,8,0,5,2,0,1,0,9},

                         {0,0,0,6,7,4,0,5,0},
                         {0,0,0,0,0,0,0,0,0},
                         {0,1,0,3,5,9,0,0,0},

                         {1,0,5,0,4,7,0,9,0},
                         {0,0,0,9,0,2,7,1,0},
                         {2,9,0,0,0,0,0,0,0} };

   solve(testBoard);
   }

 public static void main(String args[])
   {
   Sudoku sudoku = new Sudoku();

   sudoku.test();
   sudoku.test2();
   }
}
Roedy Green - 28 Dec 2005 17:19 GMT
>  /* Used to sort the cells in order of remaining possibilities. */
>    private class CellComparator implements Comparator {
[quoted text clipped - 3 lines]
>            return c2.digitRuledOutCount - c1.digitRuledOutCount;
>        }

see http://mindprod.com/jgloss/comparator.html
for how to generify this code to get rid of the error messages.

see also http://mindprod.com/jgloss/generics.html
Signature

Canadian Mind Products, Roedy Green.
http://mindprod.com Java custom programming, consulting and coaching.

bherbst65@hotmail.com - 29 Dec 2005 04:13 GMT
Hi All,
Well, well !!!
What a stunning output. I must have fell upon the
secret code.

Looking for a possible link within the program that
Patrick May gave me above, so as to get a visible
solution,  I inserted this:
............... snip........
 public void test()
   {
       int[][] testBoard = { {0,6,0,1,0,4,0,5,0},
           {0,0,8,3,0,5,6,0,0},
           {2,0,0,0,0,0,0,0,1},

           {8,0,0,4,0,7,0,0,6},
           {0,0,6,0,0,0,3,0,0},
           {7,0,0,9,0,1,0,0,4},

           {5,0,0,0,0,0,0,0,2},
           {0,0,7,2,0,6,9,0,0},
           {0,4,0,5,0,8,0,7,0} };

       solve(testBoard);

       int c=0;
       for(int xc = 0; xc< 9; xc++){
           for(int yc = 0; yc < 9; yc++){
               System.out.println(c+". "+ board[xc][yc]);
               c++;
           }
       }
   }
............... end of snip........

and the output  at this point is:

0. Sudoku$Cell@1f243d1
1. Sudoku$Cell@767286
2. Sudoku$Cell@e9aa13
3. Sudoku$Cell@1f195fc

...............
61. Sudoku$Cell@120b2da
62. Sudoku$Cell@14426a6
63. Sudoku$Cell@5b38d7
64. Sudoku$Cell@528780
65. Sudoku$Cell@5cc942
66. Sudoku$Cell@1c01ba9
67. Sudoku$Cell@23d275
68. Sudoku$Cell@c135d6
69. Sudoku$Cell@19c4091
70. Sudoku$Cell@e7d53

...............
76. Sudoku$Cell@11e1bbf
77. Sudoku$Cell@bfd66a
78. Sudoku$Cell@175b7f9
79. Sudoku$Cell@a010ba
80. Sudoku$Cell@ae1cf

What is the meaning of this or how can I see a output that I can use?

Bob
IchBin - 29 Dec 2005 04:37 GMT
> Hi All,
> Well, well !!!
[quoted text clipped - 60 lines]
>
> Bob

Don't have a clue..

Looks like interrupted address displacements into
Sudoku.Cell

For that class Sudoku$Cell do you have a getter\accessors to display
something.. and  not the whole object.  Problem definitely in
solve(testBoard); What are you doing in solve()..

A debugger would help out a lot.

Signature

Thanks in Advance...
IchBin, Pocono Lake, Pa, USA
http://weconsultants.servebeer.com/JHackerAppManager
__________________________________________________________________________

'If there is one, Knowledge is the "Fountain of Youth"'
-William E. Taylor,  Regular Guy (1952-)

Rhino - 29 Dec 2005 05:02 GMT
> Hi All,
> Well, well !!!
[quoted text clipped - 58 lines]
>
> What is the meaning of this or how can I see a output that I can use?

These are references to something, possibly arrays or other structures that
occur in each cell. But Patrick May's code doesn't contain a single
System.out.println() so I'm not sure what the code is trying to print. I'm
guessing that you've added some code to do the printing; please post this
code so that someone can tell you what you did wrong.

I expect that it will be quite simple to fix it if you show us the code that
is writing these lines.

Rhino
bherbst65@hotmail.com - 29 Dec 2005 06:30 GMT
Hi Rhino,

Please know that I tried many different ways  to "get the complete
final answer" to display. But nothing seemed to work except as written
in the program.

At your request, here is the complete program. It compiles without
error.

import java.util.*;

public class Sudoku
{
   private Cell[][] squareContents;
   private ArrayList<Cell> remainingCells = new ArrayList<Cell>();
   private int lastSort;

   // Used to sort the cells in order of remaining possibilities.
   private class CellComparator implements Comparator<Cell>
   {
       public int compare(Cell cell1,Cell cell2)
       {
           return cell2.digitRuledOutCount - cell1.digitRuledOutCount;

       }
   }

   private CellComparator comp = new CellComparator();
   public static void main(String args[])
   {
       Sudoku sudoku = new Sudoku();
       System.out.println("Here 1");
       sudoku.test();

       System.out.println("Here 2");
       sudoku.test2();

   }

   // Information about a single cell.
   public class Cell
   {
       private int x;
       private int y;
       public int inSquare;
       public int[] digitRuledOut;
       public int digitRuledOutCount;
       public int value;

       public Cell(int x,int y)
       {
           this.x = x;
           this.y = y;
           this.inSquare = 3 * (x / 3) + (y / 3);
           this.digitRuledOutCount = 9;
           this.digitRuledOut = new int[10];
           this.value = 0;
       }

       // Rules out digit v in this cell.
       private boolean ruleOutDigit(int v,int depth)
       {
           if (value == 0 && digitRuledOut[v] == 0)
           {
               digitRuledOut[v] = depth;
               if (--digitRuledOutCount == 0)
                   return true;
           }
           return false;
       }

       // Rules in digit v in this cell.
       private void ruleInDigit(int v,int depth)
       {
           if (digitRuledOut[v] == depth)
           {
               digitRuledOut[v] = 0;
               digitRuledOutCount++;
           }
       }

       // Sets the value of this cell and rules it out in other cells.

       public boolean setValue(int value,int depth)
       {
           this.value = value;
           for(int i = 0; i < 9; i++)
           {
               if (board[x][i].ruleOutDigit(value,depth))
                   return true;
               if (board[i][y].ruleOutDigit(value,depth))
                   return true;
               if
(squareContents[inSquare][i].ruleOutDigit(value,depth))
                   return true;
           }
           return false;
       }

       // Erases the value of this cell, ruling it in in other cells.
       public void eraseValue(int depth)
       {
           for(int i = 0; i < 9; i++)
           {
               board[x][i].ruleInDigit(value,depth);
               board[i][y].ruleInDigit(value,depth);
               squareContents[inSquare][i].ruleInDigit(value,depth);
           }

           this.value = 0;
       }
   }

   public Cell[][] board;

   // Initialize the solver.
   public boolean solve(int[][] initBoard)
   {
       board = new Cell[9][9];
       squareContents = new Cell[9][9];
       int[] squareCount = new int[9];

       for(int x = 0; x < 9; x++)
           for(int y = 0; y < 9; y++)
       {
           Cell c = new Cell(x,y);
           board[x][y] = c;
           squareContents[c.inSquare][squareCount[c.inSquare]++] =
               board[x][y];

       }

       for(int x = 0; x < 9; x++)
           for(int y = 0; y < 9; y++)
           if (initBoard[x][y] > 0)
           board[x][y].setValue(initBoard[x][y],100);
       else
           remainingCells.add(board[x][y]);

       Collections.sort(remainingCells,comp);
       return backtrack(1);
   }

   // The backtracking search algorithm.
   public boolean backtrack(int depth)
   {
       if (remainingCells.isEmpty())
           return true;
       if (depth == lastSort + 5 || depth == lastSort - 5)
       {
           Collections.sort(remainingCells,comp);
           lastSort = depth;
       }
       Cell current =
(Cell)remainingCells.remove(remainingCells.size()-1);

       for(int v = 1; v <= 9; v++)
       {
           if (current.digitRuledOut[v] != 0)
               continue;

           if (current.setValue(v,depth))
               current.eraseValue(depth);
           else
           {
               if (backtrack(depth + 1))
                   return true;

               current.eraseValue(depth);
           }
       }

       remainingCells.add(current);
       return false;
   }

   // A few test boards.
   public void test()
   {
       int[][] testBoard = { {0,6,0,1,0,4,0,5,0},
           {0,0,8,3,0,5,6,0,0},
           {2,0,0,0,0,0,0,0,1},

           {8,0,0,4,0,7,0,0,6},
           {0,0,6,0,0,0,3,0,0},
           {7,0,0,9,0,1,0,0,4},

           {5,0,0,0,0,0,0,0,2},
           {0,0,7,2,0,6,9,0,0},
           {0,4,0,5,0,8,0,7,0} };

       solve(testBoard);
       int c=0;
       for(int xc = 0; xc< 9; xc++){
           for(int yc = 0; yc < 9; yc++){
               System.out.println(c+". "+ board[xc][yc]);
               c++;
           }
       }
   }

   public void test2()
   {
       int[][] testBoard = { {0,0,0,0,0,0,0,3,8},
           {0,2,3,4,0,8,0,0,0},
           {0,8,0,5,2,0,1,0,9},

           {0,0,0,6,7,4,0,5,0},
           {0,0,0,0,0,0,0,0,0},
           {0,1,0,3,5,9,0,0,0},

           {1,0,5,0,4,7,0,9,0},
           {0,0,0,9,0,2,7,1,0},
           {2,9,0,0,0,0,0,0,0} };
       solve(testBoard);
       int d = 0;
       for(int xc = 0; xc< 9; xc++){
           for(int yc = 0; yc < 9; yc++){
               System.out.println(d+". "+ board[xc][yc]);
               d++;
           }
       }
   }
}
IchBin - 29 Dec 2005 09:22 GMT
> Hi Rhino,
>
[quoted text clipped - 4 lines]
> At your request, here is the complete program. It compiles without
> error.

[snip]
>         for(int xc = 0; xc< 9; xc++){
>             for(int yc = 0; yc < 9; yc++){
[quoted text clipped - 4 lines]
>     }
> }

I still think you need an accessors\getter() in your Cell Class to
return the Cell.value data. Add this to you Cell Class..

public int getCellValue( ) {
    return this.value;
 }

Presently you issue

     System.out.println(d+". "+ board[xc][yc]);

You are printing out the Cell Class object that is at any particular
position in board[xc][yc]. You want the Cell Class value.

So with a getCellValue( ) your print statement would look like this

System.out.println(d+". "+ board[xc][yc].getCellValue( ));

I ran you code with the Cell.getCellValue( ) method and this is my output

Here 1
0. 9
1. 6
2. 3
3. 1
4. 7
5. 4
6. 2
7. 5
8. 8
9. 1
10. 7
11. 8
12. 3
13. 2
14. 5
15. 6
16. 4
17. 9
18. 2
19. 5
20. 4
21. 6
22. 8
23. 9
24. 7
25. 3
26. 1
27. 8
28. 2
29. 1
30. 4
31. 3
32. 7
33. 5
34. 9
35. 6
36. 4
37. 9
38. 6
39. 8
40. 5
41. 2
42. 3
43. 1
44. 7
45. 7
46. 3
47. 5
48. 9
49. 6
50. 1
51. 8
52. 2
53. 4
54. 5
55. 8
56. 9
57. 7
58. 1
59. 3
60. 4
61. 6
62. 2
63. 3
64. 1
65. 7
66. 2
67. 4
68. 6
69. 9
70. 8
71. 5
72. 6
73. 4
74. 2
75. 5
76. 9
77. 8
78. 1
79. 7
80. 3
Here 2
0. 4
1. 5
2. 1
3. 7
4. 9
5. 6
6. 2
7. 3
8. 8
9. 9
10. 2
11. 3
12. 4
13. 1
14. 8
15. 5
16. 7
17. 6
18. 7
19. 8
20. 6
21. 5
22. 2
23. 3
24. 1
25. 4
26. 9
27. 8
28. 3
29. 2
30. 6
31. 7
32. 4
33. 9
34. 5
35. 1
36. 5
37. 7
38. 9
39. 2
40. 8
41. 1
42. 4
43. 6
44. 3
45. 6
46. 1
47. 4
48. 3
49. 5
50. 9
51. 8
52. 2
53. 7
54. 1
55. 6
56. 5
57. 8
58. 4
59. 7
60. 3
61. 9
62. 2
63. 3
64. 4
65. 8
66. 9
67. 6
68. 2
69. 7
70. 1
71. 5
72. 2
73. 9
74. 7
75. 1
76. 3
77. 5
78. 6
79. 8
80. 4

Thanks in Advance...
IchBin, Pocono Lake, Pa, USA
http://weconsultants.servebeer.com/JHackerAppManager
__________________________________________________________________________

'If there is one, Knowledge is the "Fountain of Youth"'
-William E. Taylor,  Regular Guy (1952-)
Patrick May - 29 Dec 2005 09:09 GMT
>         int c=0;
>         for(int xc = 0; xc< 9; xc++){
[quoted text clipped - 12 lines]
> 2. Sudoku$Cell@e9aa13
> 3. Sudoku$Cell@1f195fc

    The array elements you are printing out are of type Cell, an
inner class of the class Sudoku.  Cell has a public data member named
value.  That is what you want to print.

Regards,

Patrick

------------------------------------------------------------------------
S P Engineering, Inc.    | The experts in large scale distributed OO
                        | systems design and implementation.
         pjm@spe.com    | (C++, Java, Common Lisp, Jini, CORBA, UML)
bherbst65@hotmail.com - 30 Dec 2005 07:54 GMT
Thanks to all of you.

Looking at this original program, it is the most "?" that I have ever
seen. I truly
appreciate  your help, IchBin and others for  getting the solution to
be printed out.

As by changed design, I have done revisions by reading "in.txt" file
and after processing
writing an "out.txt" file.  Should there be an error/revisions in the
input then it can be
corrected by accessing the "in.txt" without doing a large amount of re
entering of the 81
numbers.

Thanks again,

Bob

import java.util.*;
import java.io.*;

public class SudokuReadWriteFile
{
   private Cell[][] squareContents;
   private ArrayList<Cell> remainingCells = new ArrayList<Cell>();
   private int lastSort;

   // Used to sort the cells in order of remaining possibilities.
   private class CellComparator implements Comparator<Cell>
   {
       public int compare(Cell cell1,Cell cell2)
       {
           return cell2.digitRuledOutCount - cell1.digitRuledOutCount;
       }
   }

   private CellComparator comp = new CellComparator();

   // main
   public static void main(String args[] ) throws Exception
   {
       SudokuReadWriteFile sudokrw = new SudokuReadWriteFile();
       //System.out.println("Here 1");
       sudokrw.test();
   }

   // Information about a single cell.
   public class Cell
   {
       private int x;
       private int y;
       public int inSquare;
       public int[] digitRuledOut;
       public int digitRuledOutCount;
       public int value;

       public Cell(int x,int y)
       {
           this.x = x;
           this.y = y;
           this.inSquare = 3 * (x / 3) + (y / 3);
           this.digitRuledOutCount = 9;
           this.digitRuledOut = new int[10];
           this.value = 0;

       }

       // Rules out digit v in this cell.
       private boolean ruleOutDigit(int v,int depth)
       {
           if (value == 0 && digitRuledOut[v] == 0)
           {
               digitRuledOut[v] = depth;
               if (--digitRuledOutCount == 0)
                   return true;
           }
           return false;
       }

       // Rules in digit v in this cell.
       private void ruleInDigit(int v,int depth)
       {
           if (digitRuledOut[v] == depth)
           {
               digitRuledOut[v] = 0;
               digitRuledOutCount++;
           }
       }

       // Sets the value of this cell and rules it out in other cells.
       public boolean setValue(int value,int depth)
       {
           this.value = value;
           for(int i = 0; i < 9; i++)
           {
               if (board[x][i].ruleOutDigit(value,depth))
                   return true;
               if (board[i][y].ruleOutDigit(value,depth))
                   return true;
               if
(squareContents[inSquare][i].ruleOutDigit(value,depth))
                   return true;
           }
           return false;
       }

       // Note : Added this to extract value of cell
       public int getCellValue( ) {
           return this.value;
       }

       // Erases the value of this cell, ruling it in in other cells.
       public void eraseValue(int depth)
       {
           for(int i = 0; i < 9; i++)
           {
               board[x][i].ruleInDigit(value,depth);
               board[i][y].ruleInDigit(value,depth);
               squareContents[inSquare][i].ruleInDigit(value,depth);
           }
           this.value = 0;
       }
   }

   public Cell[][] board;
   // Initialize the solver.
   public boolean solve(int[][] initBoard)
   {
       board = new Cell[9][9];
       squareContents = new Cell[9][9];
       int[] squareCount = new int[9];

       for(int x = 0; x < 9; x++)
           for(int y = 0; y < 9; y++)
       {
           Cell c = new Cell(x,y);
           board[x][y] = c;
           squareContents[c.inSquare][squareCount[c.inSquare]++] =
               board[x][y];
       }

       for(int x = 0; x < 9; x++)
           for(int y = 0; y < 9; y++)
           if (initBoard[x][y] > 0)
           board[x][y].setValue(initBoard[x][y],100);
       else
           remainingCells.add(board[x][y]);

       Collections.sort(remainingCells,comp);
       return backtrack(1);
   }

   // The backtracking search algorithm.
   public boolean backtrack(int depth)
   {
       if (remainingCells.isEmpty())
           return true;
       if (depth == lastSort + 5 || depth == lastSort - 5)
       {
           Collections.sort(remainingCells,comp);
           lastSort = depth;
       }
       Cell current =
(Cell)remainingCells.remove(remainingCells.size()-1);

       for(int v = 1; v <= 9; v++)
       {
           if (current.digitRuledOut[v] != 0)
               continue;

           if (current.setValue(v,depth))
               current.eraseValue(depth);
           else
           {
               if (backtrack(depth + 1))
                   return true;

               current.eraseValue(depth);
           }
       }

       remainingCells.add(current);
       return false;
   }
   // get stored file
   public void test()
   {
       try{
           FileInputStream  fis= new FileInputStream("MySudoku.txt");
           BufferedReader bor = new BufferedReader(new
InputStreamReader(fis));
           String str ="";
           int[][] testBoard= new int[9][9];
           for(int i=0; i<9; i++) {
               str = bor.readLine();
               for(int j=0; j<9; j++){
                   testBoard[i][j] =
Integer.parseInt(str.substring(j, j+1));
                   System.out.println (testBoard[i][j]);

               }
           }
           bor.close();
           solve(testBoard);

       }
       catch (Exception e) {
           System.out.println("error getting data");
       }

       // be sure to add above    public int getCellValue( ) {  return
this.value; }
       // Getting output, saving it to file and showing it in the
System.out.

       System.out.println("Saving TestBoard 1");

       try {
           FileOutputStream  fos= new
FileOutputStream("MySudokuSolution.txt");
           BufferedWriter bow = new BufferedWriter(new
OutputStreamWriter(fos));
           bow.write("{");
           for(int xc = 0; xc< 9; xc++){
               bow.write("{");
               for(int yc = 0; yc < 9; yc++){
                   if(yc == 8){
                       bow.write( board[xc][yc].getCellValue( )+" ");
                   }
                   else  bow.write( board[xc][yc].getCellValue(
)+",");
               }
               if(xc == 8){
                   bow.write( "}}"+"\n"+"\n");
               }
               else bow.write( "},"+"\n"+"\n");
           }
           bow.close();
       }
       catch (IOException ioe) {
           System.out.println("IOException writing
MySudokuSolution.txt");
       }

       System.out.println("Show System Out of TestBoard 1");

       System.out.print("{");
       for(int xc = 0; xc< 9; xc++){
           System.out.print("{");
           for(int yc = 0; yc < 9; yc++){
               if(yc== 8){
                   System.out.print( board[xc][yc].getCellValue( ));
               }
               else  System.out.print( board[xc][yc].getCellValue(
)+",");
           }
           if(xc== 8){
               System.out.print( "}}"+"\n");
           }
           else System.out.println( "},");
       }
   }
}
MySudoku.txt

060104050
008305600
200000001
800407006
006000300
700901004
500000002
007206900
040508070

MySudokuSolution.txt

{{9,6,3,1,7,4,2,5,8 },

{1,7,8,3,2,5,6,4,9 },

{2,5,4,6,8,9,7,3,1 },

{8,2,1,4,3,7,5,9,6 },

{4,9,6,8,5,2,3,1,7 },

{7,3,5,9,6,1,8,2,4 },

{5,8,9,7,1,3,4,6,2 },

{3,1,7,2,4,6,9,8,5 },

{6,4,2,5,9,8,1,7,3 }}


Free Magazines

Get these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...

Oracle MagazineNetwork ComputingComputer WorldBio-IT WorldeWeekInformation WeekInfosecurity
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2008 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.