Solving Sudoku using java swing and junit (42¢)

Solving Sudoku using java swing and junit

Was working on sudoku puzzles during easter holiday. Became bored, and being the nerd I am decided to practice my swing and created a tool to help solve it. Keep in mind that this is a “quickie” job, created in couple days work. Just extract jSudokuSolver.zip and run:

java -jar jSudoku.jar

Comes with one predefined sample.

Feel free to use the source for whatever you wish. If you want you can clone the git repo http://github.com/kenglxn/JSudoku:

git clone git://github.com/kenglxn/JSudoku.git

I based my implementation on a sudoku puzzle found in a magazine. I picked a puzzle from the magazine and made this the sample. Then i wrote a test to confirm the solver worked for the two axis, and the sub-grid. Then the last test to confirm the solver get’s the expected solution. Code for the test is pasted below.

Heres the sample:

And here’s the sample solved:

This is the recursive method that does all the work:

void solvePuzzle(Integer numberOfEmptyCellsBefore) {
	createWorkingSetOfShallowCopyCells();
	calculatePossibleValuesAndSetCellValues();
	commitChangesToAllCells();

	Integer numberOfEmptyCells = getNumberOfEmptyCellsInGrid();
	if (!numberOfEmptyCells.equals(numberOfEmptyCellsBefore)) {
		solvePuzzle(numberOfEmptyCells);
	}
}

Heres a paste of the junit test that i used to build the logic:

package net.glxn.sudoku;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;

public class JSudokuTestCase {
    @Test
    public void shouldSolveforXSibling() {
        String expected = "9";

        JSudoku jSudoku = new JSudoku();
        ArrayList<Cell> xSiblings = jSudoku.textField9.xSiblings;
        ArrayList<String> stringList = new ArrayList<String>();
        stringList.addAll(Arrays.asList("1", "2", "3", "4", "5", "6", "7", "8"));

        for (Cell xSib : xSiblings) {
            xSib.setText(stringList.get(0));
            stringList.remove(0);
        }

        jSudoku.solvePuzzle(jSudoku.getNumberOfEmptyCellsInGrid());

        Assert.assertEquals(expected, jSudoku.textField9.getText());
    }

    @Test
    public void shouldSolveforYSibling() {
        String expected = "9";

        JSudoku jSudoku = new JSudoku();
        ArrayList<Cell> ysiblings = jSudoku.textField9.ySiblings;
        ArrayList<String> stringList = new ArrayList<String>();
        stringList.addAll(Arrays.asList("1", "2", "3", "4", "5", "6", "7", "8"));

        for (Cell ySib : ysiblings) {
            ySib.setText(stringList.get(0));
            stringList.remove(0);
        }

        jSudoku.solvePuzzle(jSudoku.getNumberOfEmptyCellsInGrid());

        Assert.assertEquals(expected, jSudoku.textField9.getText());
    }

    @Test
    public void shouldSolveforSubGridSibling() {
        String expected = "9";

        JSudoku jSudoku = new JSudoku();
        ArrayList<Cell> ysiblings = jSudoku.textField9.subGridSiblings;
        ArrayList<String> stringList = new ArrayList<String>();
        stringList.addAll(Arrays.asList("1", "2", "3", "4", "5", "6", "7", "8"));

        for (Cell ySib : ysiblings) {
            ySib.setText(stringList.get(0));
            stringList.remove(0);
        }

        jSudoku.solvePuzzle(jSudoku.getNumberOfEmptyCellsInGrid());

        Assert.assertEquals(expected, jSudoku.textField9.getText());
    }

    @Test
    public void shouldBeAbleToSolveSample() {
        JSudoku jSudoku = new JSudoku();
        jSudoku.loadSample();

        confirmSample(jSudoku);

        jSudoku.solvePuzzle(jSudoku.getNumberOfEmptyCellsInGrid());

        confirmWholeGrid(jSudoku);
    }

    private void confirmSample(JSudoku jSudoku) {
        confirmExpectedValueAtCoord(jSudoku, 2, 1, 1);
        confirmExpectedValueAtCoord(jSudoku, 4, 1, 9);
        confirmExpectedValueAtCoord(jSudoku, 5, 1, 5);
        confirmExpectedValueAtCoord(jSudoku, 7, 1, 7);

        confirmExpectedValueAtCoord(jSudoku, 2, 2, 5);
        confirmExpectedValueAtCoord(jSudoku, 5, 2, 3);

        confirmExpectedValueAtCoord(jSudoku, 2, 3, 9);
        confirmExpectedValueAtCoord(jSudoku, 4, 3, 6);
        confirmExpectedValueAtCoord(jSudoku, 9, 3, 5);

        confirmExpectedValueAtCoord(jSudoku, 1, 4, 2);
        confirmExpectedValueAtCoord(jSudoku, 3, 4, 6);
        confirmExpectedValueAtCoord(jSudoku, 6, 4, 8);

        confirmExpectedValueAtCoord(jSudoku, 3, 5, 8);
        confirmExpectedValueAtCoord(jSudoku, 7, 5, 4);

        confirmExpectedValueAtCoord(jSudoku, 4, 6, 3);
        confirmExpectedValueAtCoord(jSudoku, 7, 6, 6);
        confirmExpectedValueAtCoord(jSudoku, 9, 6, 9);

        confirmExpectedValueAtCoord(jSudoku, 1, 7, 4);
        confirmExpectedValueAtCoord(jSudoku, 6, 7, 3);
        confirmExpectedValueAtCoord(jSudoku, 8, 7, 5);

        confirmExpectedValueAtCoord(jSudoku, 5, 8, 8);
        confirmExpectedValueAtCoord(jSudoku, 8, 8, 6);

        confirmExpectedValueAtCoord(jSudoku, 3, 9, 1);
        confirmExpectedValueAtCoord(jSudoku, 5, 9, 4);
        confirmExpectedValueAtCoord(jSudoku, 6, 9, 5);
        confirmExpectedValueAtCoord(jSudoku, 8, 9, 2);
    }

    private void confirmWholeGrid(JSudoku jSudoku) {
        confirmExpectedValueAtCoord(jSudoku, 1, 1, 8);
        confirmExpectedValueAtCoord(jSudoku, 2, 1, 1);
        confirmExpectedValueAtCoord(jSudoku, 3, 1, 2);
        confirmExpectedValueAtCoord(jSudoku, 4, 1, 9);
        confirmExpectedValueAtCoord(jSudoku, 5, 1, 5);
        confirmExpectedValueAtCoord(jSudoku, 6, 1, 4);
        confirmExpectedValueAtCoord(jSudoku, 7, 1, 7);
        confirmExpectedValueAtCoord(jSudoku, 8, 1, 3);
        confirmExpectedValueAtCoord(jSudoku, 9, 1, 6);

        confirmExpectedValueAtCoord(jSudoku, 1, 2, 6);
        confirmExpectedValueAtCoord(jSudoku, 2, 2, 5);
        confirmExpectedValueAtCoord(jSudoku, 3, 2, 4);
        confirmExpectedValueAtCoord(jSudoku, 4, 2, 8);
        confirmExpectedValueAtCoord(jSudoku, 5, 2, 3);
        confirmExpectedValueAtCoord(jSudoku, 6, 2, 7);
        confirmExpectedValueAtCoord(jSudoku, 7, 2, 2);
        confirmExpectedValueAtCoord(jSudoku, 8, 2, 9);
        confirmExpectedValueAtCoord(jSudoku, 9, 2, 1);

        confirmExpectedValueAtCoord(jSudoku, 1, 3, 7);
        confirmExpectedValueAtCoord(jSudoku, 2, 3, 9);
        confirmExpectedValueAtCoord(jSudoku, 3, 3, 3);
        confirmExpectedValueAtCoord(jSudoku, 4, 3, 6);
        confirmExpectedValueAtCoord(jSudoku, 5, 3, 2);
        confirmExpectedValueAtCoord(jSudoku, 6, 3, 1);
        confirmExpectedValueAtCoord(jSudoku, 7, 3, 8);
        confirmExpectedValueAtCoord(jSudoku, 8, 3, 4);
        confirmExpectedValueAtCoord(jSudoku, 9, 3, 5);

        confirmExpectedValueAtCoord(jSudoku, 1, 4, 2);
        confirmExpectedValueAtCoord(jSudoku, 2, 4, 7);
        confirmExpectedValueAtCoord(jSudoku, 3, 4, 6);
        confirmExpectedValueAtCoord(jSudoku, 4, 4, 4);
        confirmExpectedValueAtCoord(jSudoku, 5, 4, 9);
        confirmExpectedValueAtCoord(jSudoku, 6, 4, 8);
        confirmExpectedValueAtCoord(jSudoku, 7, 4, 5);
        confirmExpectedValueAtCoord(jSudoku, 8, 4, 1);
        confirmExpectedValueAtCoord(jSudoku, 9, 4, 3);

        confirmExpectedValueAtCoord(jSudoku, 1, 5, 9);
        confirmExpectedValueAtCoord(jSudoku, 2, 5, 3);
        confirmExpectedValueAtCoord(jSudoku, 3, 5, 8);
        confirmExpectedValueAtCoord(jSudoku, 4, 5, 5);
        confirmExpectedValueAtCoord(jSudoku, 5, 5, 1);
        confirmExpectedValueAtCoord(jSudoku, 6, 5, 6);
        confirmExpectedValueAtCoord(jSudoku, 7, 5, 4);
        confirmExpectedValueAtCoord(jSudoku, 8, 5, 7);
        confirmExpectedValueAtCoord(jSudoku, 9, 5, 2);

        confirmExpectedValueAtCoord(jSudoku, 1, 6, 1);
        confirmExpectedValueAtCoord(jSudoku, 2, 6, 4);
        confirmExpectedValueAtCoord(jSudoku, 3, 6, 5);
        confirmExpectedValueAtCoord(jSudoku, 4, 6, 3);
        confirmExpectedValueAtCoord(jSudoku, 5, 6, 7);
        confirmExpectedValueAtCoord(jSudoku, 6, 6, 2);
        confirmExpectedValueAtCoord(jSudoku, 7, 6, 6);
        confirmExpectedValueAtCoord(jSudoku, 8, 6, 8);
        confirmExpectedValueAtCoord(jSudoku, 9, 6, 9);

        confirmExpectedValueAtCoord(jSudoku, 1, 7, 4);
        confirmExpectedValueAtCoord(jSudoku, 2, 7, 8);
        confirmExpectedValueAtCoord(jSudoku, 3, 7, 9);
        confirmExpectedValueAtCoord(jSudoku, 4, 7, 2);
        confirmExpectedValueAtCoord(jSudoku, 5, 7, 6);
        confirmExpectedValueAtCoord(jSudoku, 6, 7, 3);
        confirmExpectedValueAtCoord(jSudoku, 7, 7, 1);
        confirmExpectedValueAtCoord(jSudoku, 8, 7, 5);
        confirmExpectedValueAtCoord(jSudoku, 9, 7, 7);

        confirmExpectedValueAtCoord(jSudoku, 1, 8, 5);
        confirmExpectedValueAtCoord(jSudoku, 2, 8, 2);
        confirmExpectedValueAtCoord(jSudoku, 3, 8, 7);
        confirmExpectedValueAtCoord(jSudoku, 4, 8, 1);
        confirmExpectedValueAtCoord(jSudoku, 5, 8, 8);
        confirmExpectedValueAtCoord(jSudoku, 6, 8, 9);
        confirmExpectedValueAtCoord(jSudoku, 7, 8, 3);
        confirmExpectedValueAtCoord(jSudoku, 8, 8, 6);
        confirmExpectedValueAtCoord(jSudoku, 9, 8, 4);

        confirmExpectedValueAtCoord(jSudoku, 1, 9, 3);
        confirmExpectedValueAtCoord(jSudoku, 2, 9, 6);
        confirmExpectedValueAtCoord(jSudoku, 3, 9, 1);
        confirmExpectedValueAtCoord(jSudoku, 4, 9, 7);
        confirmExpectedValueAtCoord(jSudoku, 5, 9, 4);
        confirmExpectedValueAtCoord(jSudoku, 6, 9, 5);
        confirmExpectedValueAtCoord(jSudoku, 7, 9, 9);
        confirmExpectedValueAtCoord(jSudoku, 8, 9, 2);
        confirmExpectedValueAtCoord(jSudoku, 9, 9, 8);
    }

    private void confirmExpectedValueAtCoord(JSudoku jSudoku, int x, int y, Integer expected) {
        Assert.assertEquals("Confirm ["+x+","+y+"] = "+ expected, expected, jSudoku.getCellAtCoord(x, y, jSudoku.allCells).getIntValue());
    }

12 Sep 2017		Building an executable WS client using maven and metro
07 Jun 2015		Deploy an Ember app to gh-pages using npm run-script
06 Jun 2015		JSON Contract testing using unit tests to assert full stack integration across REST services
03 May 2015		simple http serve a directory from terminal
07 Jan 2014		civu, a CLI for cloning git repositories from jenkins views
06 Jan 2014		PyramidSort, a Sublime Text plugin for for reformatting text
05 Jan 2014		Git commit-message hook for JIRA issue tags
31 May 2013		hacking kitchen tiles with coffeescript
30 May 2013		Nuke, ps grep kill something
24 May 2013		mvnr: recursive mvn command runner
23 May 2013		Query By Example for JPA
22 May 2013		gitr: recursive git command runner
21 May 2013		Keeping gh-pages branch in sync with master
19 May 2013		Migrated from wordpress to jekyll and github pages
14 Aug 2012		Using Sublime Text 2 as git commit message editor
10 Mar 2012		QRGen, a small wrapper on top of ZXING for generating QRCodes in java
04 Jan 2012		My Bash PS1 with git branch info
17 Aug 2010		Making a swing project using IntelliJ IDEA GUI builder with maven, Including executable jar
01 May 2010		Using Arquillian to test against a remote jboss container from within IDEA
06 Apr 2010		WELD/CDI lightningtalk from Know IT 2010 annual conference
03 Apr 2010		Solving Sudoku using java swing and junit
01 Mar 2010		Simple CDI/WELD login example
01 Mar 2010		Implementing @RequestParam in CDI/WELD using Qualifier and InjectionPoint as @HttpParam
01 Nov 2009		Seam Maven Refimpl

42¢ glxn.net

Solving Sudoku using java swing and junit

Moar stuffs