aspose file tools*
The moose likes Java in General and the fly likes Sudoku Solver Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Sudoku Solver " Watch "Sudoku Solver " New topic
Author

Sudoku Solver

wadshariff kassala
Greenhorn

Joined: Oct 29, 2008
Posts: 1
Hi

I'm trying to solve a sudoku puzzle by puting the missing digit in the empty box. I'm using Junit to do the test, the code run but it doesn't print the completed box.

thanks

*_--------------_* my code;

package sudoku;

import org.junit.After;
import org.junit.Before;
import org.junit.Test;
import static org.junit.Assert.*;

/**
*
*
* Draft tests.... now in JUnit 4.x format
*/
public class SudokuTest{

// runs before each test
@Before
public void setUp() {
}

// runs after each test
@After
public void tearDown() {
}

/**
* Test of solve method, of class Sudoku.
*/
@Test
public void solve() {
int[][] puzzle =
{{0, 0, 8, 6, 0, 4, 3, 0,0},
{0, 4, 0, 0, 7, 0, 0, 1, 0},
{7, 0, 0, 0, 0, 0, 0, 0, 2},
{4, 0, 0, 0, 8, 0, 0, 0, 9},
{0, 1, 0, 9, 0, 5, 0, 3, 0},
{3, 0, 0, 0, 2, 0, 0, 0, 1},
{6, 0, 0, 0, 0, 0, 0, 0, 5},
{0, 5, 0, 0, 3, 0, 0, 9, 0},
{0, 0, 2, 1, 0, 6, 7, 0, 0}};

int[][] expResult =
{{2, 9, 8, 6, 1, 4, 3, 5, 7},
{5, 4, 6, 2, 7, 3, 9, 1, 8},
{7, 3, 1, 5, 9, 8, 4, 6, 2},
{4, 2, 5, 3, 8, 1, 6, 7, 9},
{8, 1, 7, 9, 6, 5, 2, 3, 4},
{3, 6, 9, 4, 2, 7, 5, 8, 1},
{6, 7, 3, 8, 4, 9, 1, 2, 5},
{1, 5, 4, 7, 3, 2, 8, 9, 6},
{9, 8, 2, 1, 5, 6, 7, 4, 3}};

Sudoku instance = new Sudoku(puzzle);
int[][] result = instance.solve();
compare(expResult, result);

}

/**
* Cell wise comparison of the arrays
* @param expResult The expected array values
* @param result The computed array values
*/
private void compare(int[][] expResult, int[][] result) {

for (int i = 0; i < expResult.length; i++) {
for (int j = 0; j < expResult[0].length; j++) {
assertEquals(expResult[i][j], result[i][j]);
}
}
return;
}

static boolean solve(int i, int j, int[][] cells) {
if (i == 9) {
i = 0;
if (++j == 9)
return true;
}
if (cells[i][j] != 0) // skip filled cells
return solve(i+1,j,cells);

for (int val = 1; val <= 9; ++val) {
if (legal(i,j,val,cells)) {
cells[i][j] = val;
if (solve(i+1,j,cells))
return true;
}
}
cells[i][j] = 0; // reset on backtrack
return false;
}

static boolean legal(int i, int j, int val, int[][] cells) {
for (int k = 0; k < 9; ++k) // row
if (val == cells[k][j])
return false;

for (int k = 0; k < 9; ++k) // col
if (val == cells[i][k])
return false;

int boxRowOffset = (i / 3)*3;
int boxColOffset = (j / 3)*3;
for (int k = 0; k < 3; ++k) // box
for (int m = 0; m < 3; ++m)
if (val == cells[boxRowOffset+k][boxColOffset+m])
return false;

return true; // no violations, so it's legal
}







/**
* Test of getBox method, of class Sudoku.
*/
@Test
public void getBox() {
int boxRow = 1;
int boxColumn = 1;
Sudoku instance = new Sudoku(new int[][]{
{0, 0, 8, 6, 0, 4, 3, 0, 0},
{0, 4, 0, 0, 7, 0, 0, 1, 0},
{7, 0, 0, 0, 0, 0, 0, 0, 2},
{4, 0, 0, 0, 8, 0, 0, 0, 9},
{0, 1, 0, 9, 0, 5, 0, 3, 0},
{3, 0, 0, 0, 2, 0, 0, 0, 1},
{6, 0, 0, 0, 0, 0, 0, 0, 5},
{0, 5, 0, 0, 3, 0, 0, 9, 0},
{0, 0, 2, 1, 0, 6, 7, 0, 0}});
int[][] expResult = {{0, 8, 0},
{9, 0, 5},
{0, 2, 0}};
int[][] result = instance.getBox(boxRow, boxColumn);

compare(expResult, result);
}

/**
* Test of occursInRow method, of class Sudoku.
*/
@Test
public void occursInRow() {
Sudoku instance = new Sudoku(new int[][]{
{0, 0, 8, 6, 0, 4, 3, 0, 0},
{0, 4, 0, 0, 7, 0, 0, 1, 0},
{7, 0, 0, 0, 0, 0, 0, 0, 2},
{4, 0, 0, 0, 8, 0, 0, 0, 9},
{0, 1, 0, 9, 0, 5, 0, 3, 0},
{3, 0, 0, 0, 2, 0, 0, 0, 1},
{6, 0, 0, 0, 0, 0, 0, 0, 5},
{0, 5, 0, 0, 3, 0, 0, 9, 0},
{0, 0, 2, 1, 0, 6, 7, 0, 0}});
assertTrue(instance.occursInRow(4, 0));
assertFalse(instance.occursInRow(7, 0));
}

/**
* Test of occursInColumn method, of class Sudoku.
*/
@Test
public void occursInColumn() {
Sudoku instance = new Sudoku(new int[][]{
{0, 0, 8, 6, 0, 4, 3, 0, 0},
{0, 4, 0, 0, 7, 0, 0, 1, 0},
{7, 0, 0, 0, 0, 0, 0, 0, 2},
{4, 0, 0, 0, 8, 0, 0, 0, 9},
{0, 1, 0, 9, 0, 5, 0, 3, 0},
{3, 0, 0, 0, 2, 0, 0, 0, 1},
{6, 0, 0, 0, 0, 0, 0, 0, 5},
{0, 5, 0, 0, 3, 0, 0, 9, 0},
{0, 0, 2, 1, 0, 6, 7, 0, 0}});

assertTrue(instance.occursInColumn(7, 0));
assertFalse(instance.occursInColumn(5, 0));
}

/**
* Test of occursInBox method, of class Sudoku.
*/
@Test
public void occursInBox() {
System.out.println("occursInBox");
int digit = 0;
int row = 0;
int column = 0;
Sudoku instance = new Sudoku(new int[][]{
{0, 0, 8, 6, 0, 4, 3, 0, 0},
{0, 4, 0, 0, 7, 0, 0, 1, 0},
{7, 0, 0, 0, 0, 0, 0, 0, 2},
{4, 0, 0, 0, 8, 0, 0, 0, 9},
{0, 1, 0, 9, 0, 5, 0, 3, 0},
{3, 0, 0, 0, 2, 0, 0, 0, 1},
{6, 0, 0, 0, 0, 0, 0, 0, 5},
{0, 5, 0, 0, 3, 0, 0, 9, 0},
{0, 0, 2, 1, 0, 6, 7, 0, 0}});
assertTrue(instance.occursInBox(9, 8, 8));
assertFalse(instance.occursInBox(6, 8, 8));
}

/**
* Test of isPossibleDigit method, of class Sudoku.
*/
@Test
public void isPossibleDigit() {
Sudoku instance = new Sudoku(new int[][]{
{0, 0, 8, 6, 0, 4, 3, 0, 0},
{0, 4, 0, 0, 7, 0, 0, 1, 0},
{7, 0, 0, 0, 0, 0, 0, 0, 2},
{4, 0, 0, 0, 8, 0, 0, 0, 9},
{0, 1, 0, 9, 0, 5, 0, 3, 0},
{3, 0, 0, 0, 2, 0, 0, 0, 1},
{6, 0, 0, 0, 0, 0, 0, 0, 5},
{0, 5, 0, 0, 3, 0, 0, 9, 0},
{0, 0, 2, 1, 0, 6, 7, 0, 0}});
assertTrue(instance.isPossibleDigit(1, 0, 0));
assertFalse(instance.isPossibleDigit(6, 0, 0));
}

/**
* Test of isOnlyPossibleDigit method, of class Sudoku.
*/
@Test
public void isOnlyPossibleDigit() {
Sudoku instance = new Sudoku(new int[][]{
{0, 0, 8, 6, 0, 4, 3, 0, 0},
{0, 4, 0, 0, 7, 0, 0, 1, 0},
{7, 0, 0, 0, 0, 0, 0, 0, 2},
{4, 0, 0, 0, 8, 0, 0, 0, 9},
{0, 1, 0, 9, 0, 5, 0, 3, 0},
{3, 0, 0, 0, 2, 0, 0, 0, 1},
{6, 0, 0, 0, 0, 0, 0, 0, 5},
{0, 5, 0, 0, 3, 0, 0, 9, 0},
{0, 0, 2, 1, 0, 6, 7, 0, 0}});
assertTrue(instance.isOnlyPossibleDigit(2, 0, 0));
assertFalse(instance.isOnlyPossibleDigit(5, 0, 0));
}

/**
* Test of getOnlyPossibleDigit method, of class Sudoku.
*/
@Test
public void getOnlyPossibleDigit() {
Sudoku instance = new Sudoku(new int[][]{
{0, 0, 8, 6, 0, 4, 3, 0, 0},
{0, 4, 0, 0, 7, 0, 0, 1, 0},
{7, 0, 0, 0, 0, 0, 0, 0, 2},
{4, 0, 0, 0, 8, 0, 0, 0, 9},
{0, 1, 0, 9, 0, 5, 0, 3, 0},
{3, 0, 0, 0, 2, 0, 0, 0, 1},
{6, 0, 0, 0, 0, 0, 0, 0, 5},
{0, 5, 0, 0, 3, 0, 0, 9, 0},
{0, 0, 2, 1, 0, 6, 7, 0, 0}});
assertEquals(instance.getOnlyPossibleDigit(7, 0),1);//8?
assertFalse(instance.getOnlyPossibleDigit(0, 0) == 5);
}
}
[ October 29, 2008: Message edited by: wadshariff kassala ]
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11477
    
  16

Please use code tags when posting your source. it preserves the indentation, keeping things readable. you can either type them by hand:

[ CODE]

[ /CODE]

(without the space), or use the little "instant UBB" buttons you seen when making your post. click the button, and paste your code between.

Also, it really helps if you ask a focused question, and limit the code to the part where the problem seems to be. simply posting 261 lines of code and saying "This doesn't work" will probably not get you a very good response.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Jeanne Boyarsky
author & internet detective
Marshal

Joined: May 26, 2003
Posts: 30924
    
158

Also, you'll want to post the smallest possible code snippet that shows the error. For example, you have many JUnit tests. Only one of them would be needed to see the error.


[Blog] [JavaRanch FAQ] [How To Ask Questions The Smart Way] [Book Promos]
Blogging on Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, OCAJP, OCPJP beta, TOGAF part 1 and part 2
Tanu Gulati
Ranch Hand

Joined: Oct 06, 2008
Posts: 113

you can also search for sudoku in the current website just click on Search link and enter "sudoku" in the text box.
i found this one interesting


thanks
Tanu Gulati
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Sudoku Solver