• Post Reply Bookmark Topic Watch Topic
  • New Topic
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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Sudoku Solver

 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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 ]
 
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
author & internet detective
Posts: 41860
908
Eclipse IDE VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Ranch Hand
Posts: 113
Hibernate Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Attractive, successful people love this tiny ad:
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic