Re: Suduko solver demo

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

.

Relevant Pages

  • 64-bit for gcc-gnat-3.3.2
    ... s-stalib.ads:67:04: warning: types for unchecked conversion have ... different sizes ... gcc: -lgnat: linker input file unused because linking not done ...
    (comp.lang.ada)
  • Re: Hiding inherited method
    ... why is there no warning that the code may not work the ... Is it simply because the _new_ keyword turns it off? ... Without the _new_ keyword, the warning about hiding fires, but this is a case ... where no hiding will happen anyway, because the private method _does_not_ ...
    (microsoft.public.dotnet.languages.csharp)
  • warning: this used in base member initializer list
    ... I'm guessing the warning stems from the fact that I'm passing ... However, I'm not actually using 'this', just passing and storing ...
    (comp.lang.cpp)
  • Proxy/Stub Dll exported symbol Warnings
    ... I am receiving warnings during the dll proxy build step in a ATL COM server ... TESTAPPps.def: warning LNK4222: exported symbol 'DllGetClassObject' should ... DllGetClassObject @1 PRIVATE ...
    (microsoft.public.vc.atl)
  • Re: Proxy/Stub Dll exported symbol Warnings
    ... The make file output is as follows: ... TESTAPPps.def: warning LNK4222: exported symbol 'DllGetClassObject' ... DllGetClassObject @1 PRIVATE ...
    (microsoft.public.vc.atl)