Suduko solver demo
bher...@hotmail.com
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
<bher...@hotmail.com> wrote in message
news:1135703308.3...@g43g2000cwa.googlegroups.com...
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
bher...@hotmail.com
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
> 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?
--
Andrew Thompson
physci, javasaver, 1point1c, lensescapes - athompson.info/andrew
bher...@hotmail.com
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
Patrick May
> 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.
p...@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();
}
}
Rhino
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
<bher...@hotmail.com> wrote in message
news:1135784609.0...@g43g2000cwa.googlegroups.com...
Roedy Green
indirectly quoted someone who said :
> /* 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;
> }
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
--
Canadian Mind Products, Roedy Green.
http://mindprod.com Java custom programming, consulting and coaching.
bher...@hotmail.com
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
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.
--
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
<bher...@hotmail.com> wrote in message
news:1135829624.1...@g14g2000cwa.googlegroups.com...
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
bher...@hotmail.com
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++;
}
}
}
}
Patrick May
> 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
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.
IchBin
> 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.
[snip]
> for(int xc = 0; xc< 9; xc++){
> for(int yc = 0; yc < 9; yc++){
> System.out.println(d+". "+ board[xc][yc]);
> d++;
> }
> }
> }
> }
>
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
bher...@hotmail.com
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 }}