Forums Register Login

Sudoku Solver

+Pie Number of slices to send: Send
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 ]
+Pie Number of slices to send: Send
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.
+Pie Number of slices to send: Send
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.
+Pie Number of slices to send: Send
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
Montana has cold dark nights. Perfect for the heat from incandescent light. Tiny ad:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com


reply
reply
This thread has been viewed 2806 times.
Similar Threads
Something i'm extremely confused on
June Newsletter Puzzle
struct in java
Exception -- java.lang.StackOverflowError
Error from sudoku class
More...

All times above are in ranch (not your local) time.
The current ranch time is
Mar 28, 2024 10:24:08.