programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Bear Bibeault
• Devaka Cooray
• Liutauras Vilda
• Jeanne Boyarsky
Sheriffs:
• Knute Snortum
• Junilu Lacar
• paul wheaton
Saloon Keepers:
• Ganesh Patekar
• Frits Walraven
• Tim Moores
• Ron McLeod
• Carey Brown
Bartenders:
• Stephan van Hulst
• salvin francis
• Tim Holloway

# Sudoku Solver

Greenhorn
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 ]

lowercase baba
Posts: 12628
50
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.

author & internet detective
Posts: 38906
684
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.

Ranch Hand
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

 Don't get me started about those stupid light bulbs.