Java Forum / First Aid / December 2005
Suduko solver demo
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 MagazinesGet 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 ...
|
|
|