Re: Suduko solver demo

bherbst65@xxxxxxxxxxx writes:
> 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@xxxxxxx | (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();
}
}
.

Relevant Pages