• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Sudoku Solver

 
wadshariff kassala
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 12149
31
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Jeanne Boyarsky
author & internet detective
Marshal
Posts: 34695
367
Eclipse IDE Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Tanu Gulati
Ranch Hand
Posts: 113
Hibernate Java Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic