This is the source code:
- Code: Select all
import javax.microedition.lcdui.Graphics;
import lejos.nxt.Button;
import lejos.nxt.Sound;
public class SodokuSolver {
/*
This program allows you to turn your NXT in to a portable sodoku solver.
use the left and right arrows to scroll through the cells and buttons and
press enter to click the buttons or select the cells, when you select a cell
the cell indicator in the bottom right goes black, to deselect a cell press
the escape button. The logic used is rather simple, the program only checks
if there is only 1 possible number for a box or if there is only 1 possible
space for a number in a row or column, so don't be surprised if it wont solve
very hard sodoku's.
ChrisB
*/
static SodokuSolver program;
int[][] squareValues = new int[9][9];
int focus = 0;
int selected = 0;
float percentBar;
Graphics g = new Graphics();
public static void main(String[] args) {
program = new SodokuSolver();
program.squareValues[0][0] = 7;
program.squareValues[0][3] = 3;
program.squareValues[0][5] = 5;
program.squareValues[0][8] = 8;
program.squareValues[1][2] = 3;
program.squareValues[1][4] = 7;
program.squareValues[1][6] = 4;
program.squareValues[2][1] = 8;
program.squareValues[2][7] = 6;
program.squareValues[3][0] = 4;
program.squareValues[3][3] = 2;
program.squareValues[3][5] = 8;
program.squareValues[3][8] = 9;
program.squareValues[4][1] = 1;
program.squareValues[4][7] = 5;
program.squareValues[5][0] = 3;
program.squareValues[5][3] = 6;
program.squareValues[5][5] = 1;
program.squareValues[5][8] = 2;
program.squareValues[6][1] = 9;
program.squareValues[6][7] = 3;
program.squareValues[7][2] = 8;
program.squareValues[7][4] = 4;
program.squareValues[7][6] = 7;
program.squareValues[8][0] = 2;
program.squareValues[8][3] = 5;
program.squareValues[8][5] = 6;
program.squareValues[8][8] = 4;
program.gui();
program.watchButtons();
}
void gui() {
g.clear();
g.autoRefresh(false);
int cellSize = 8;
int startX = 0;
int startY = 0;
int x = 0;
int y = 0;
if (focus > 45 && focus != 82 && focus != 83 && focus != 84) {
startY = 0 - cellSize - 1;
}
while (y < 9) {
while (x < 9) {
if (focus == (x + 1) + (y * 9)) {
g.fillRect(startX + (x * cellSize), startY + (y * cellSize), cellSize, cellSize);
if (squareValues[x][y] == 0) {
g.drawString(" ", startX + (x * cellSize) + 2, startY + (y * cellSize) + 1, true);
} else {
g.drawString(Integer.toString(squareValues[y][x]), startX + (x * cellSize) + 2, startY + (y * cellSize) + 1, true);
}
if (focus == selected) {
g.drawString(Integer.toString(squareValues[y][x]), 80, 50, true);
} else {
g.drawString(Integer.toString(squareValues[y][x]), 80, 50, false);
}
} else {
g.drawRect(startX + (x * cellSize), startY + (y * cellSize), cellSize, cellSize);
if (squareValues[x][y] == 0) {
g.drawString(" ", startX + (x * cellSize) + 2, startY + (y * cellSize) + 1, false);
} else {
g.drawString(Integer.toString(squareValues[y][x]), startX + (x * cellSize) + 2, startY + (y * cellSize) + 1, false);
}
}
x++;
}
x = 0;
y++;
}
if (focus == 82) {
g.drawRect(70, 8, 29, 9);
g.drawString("Solve", 71, 9, true);
} else {
g.drawRect(74, 8, 29, 9);
g.drawString("Solve", 75, 9, false);
}
if (focus == 83) {
g.drawRect(70, 19, 29, 9);
g.drawString("Clear", 71, 20, true);
} else {
g.drawRect(74, 19, 29, 9);
g.drawString("Clear", 75, 20, false);
}
g.drawRect(74, 30, 24, 9);
if (focus == 84) {
g.drawString("Quit", 75, 31, true);
} else {
g.drawString("Quit", 75, 31, false);
}
g.refresh();
}
void drawStatus(int cellsComplete) {
g.clear();
if (cellsComplete != 0) {
g.drawString("Solving...", 28, 26);
g.drawRect(9, 50, 81, 6);
g.fillRect(9, 50, cellsComplete, 6);
g.refresh();
} else {
g.drawString("Solve Failed", 25, 26);
g.refresh();
try {
Thread.sleep(2000);
} catch (InterruptedException e) {
}
}
}
void watchButtons() {
while (true) {
if (Button.RIGHT.isPressed()) {
if (focus == 84) {
focus = 0;
} else {
focus++;
}
gui();
try {
Thread.sleep(100);
} catch (InterruptedException e) {
}
}
if (Button.LEFT.isPressed()) {
if (focus == 0) {
focus = 84;
} else {
focus--;
}
gui();
try {
Thread.sleep(100);
} catch (InterruptedException e) {
}
}
if (Button.ENTER.isPressed()) {
if (focus == 82 || focus == 83 || focus == 84) {
if (focus == 82) {
int[][] newCells = solve(squareValues);
if (newCells != null) {
Sound.beepSequenceUp();
squareValues = newCells;
gui();
} else {
Sound.beepSequence();
}
} else if (focus == 83) {
squareValues = new int[9][9];
Sound.beep();
gui();
} else if (focus == 84) {
System.exit(0);
}
} else {
while (Button.ENTER.isPressed()) {
}
if (focus != 0) {
selected = focus;
gui();
while (!Button.ESCAPE.isPressed()) {
if (Button.RIGHT.isPressed()) {
while (Button.RIGHT.isPressed()) {
}
if (squareValues[(focus - 1) % 9][(focus - 1) / 9] != 9) {
squareValues[(focus - 1) % 9][(focus - 1) / 9] = squareValues[(focus - 1) % 9][(focus - 1) / 9] + 1;
} else {
squareValues[(focus - 1) % 9][(focus - 1) / 9] = 0;
}
gui();
}
if (Button.LEFT.isPressed()) {
while (Button.LEFT.isPressed()) {
}
if (squareValues[(focus - 1) % 9][(focus - 1) / 9] != 0) {
squareValues[(focus - 1) % 9][(focus - 1) / 9] = squareValues[(focus - 1) % 9][(focus - 1) / 9] - 1;
} else {
squareValues[(focus - 1) % 9][(focus - 1) / 9] = 9;
}
gui();
}
}
while (Button.ESCAPE.isPressed()) {
}
selected = 0;
gui();
}
}
}
}
}
static boolean checkLegal(int y, int x, int val, int[][] cells) {
if (cells[y][x] != 0)
return false;
return checkCol(x, val, cells) == false && checkRow(y, val, cells) == false && checkSquare(y, x, val, cells) == false;
}
static boolean checkCol(int x, int val, int[][] cells) {
int y = 0;
while (y < 9) {
if (cells[y][x] == val) {
return true;
}
y++;
}
return false;
}
static boolean checkRow(int y, int val, int[][] cells) {
int x = 0;
while (x < 9) {
if (cells[y][x] == val)
return true;
x++;
}
return false;
}
static boolean checkSquare(int y, int x, int val, int[][] cells) {
int boxRowOffset = (x / 3) * 3;
int boxColOffset = (y / 3) * 3;
for (int k = 0; k < 3; ++k) {
for (int m = 0; m < 3; ++m) {
if (val == cells[boxColOffset + m][boxRowOffset + k]) {
return true;
}
}
}
return false;
}
static int[][] solve(int[][] cells) {
int[][] newCells = cells;
int x = 0;
int y = 0;
int cellsComplete = 0;
while (x < 9) {
while (y < 9) {
if (newCells[y][x] != 0) {
cellsComplete++;
}
y++;
}
x++;
y = 0;
}
if (cellsComplete == 0)
return new int[9][9];
program.drawStatus(cellsComplete);
int onlyPossibilty = 0;
boolean finished = false;
boolean changedSomething = true;
while (finished == false && changedSomething == true) {
x = 0;
y = 0;
finished = true;
changedSomething = false;
while (x < 9) {
while (y < 9) {
if (newCells[y][x] == 0) {
onlyPossibilty = 0;
finished = false;
int values = 1;
while (values < 10) {
// System.out.println(values);
if (checkLegal(y, x, values, newCells) == true) {
if (onlyPossibilty == 0) {
onlyPossibilty = values;
} else {
values = 10;
onlyPossibilty = 0;
}
}
values++;
}
if (onlyPossibilty != 0) {
// writeMatrix(cells);
// System.out.println("Changed:" + y + " " + x +
// " to " + onlyPossibilty + " Legal:" +
// checkLegal(y, x, onlyPossibilty, newCells));
newCells[y][x] = onlyPossibilty;
changedSomething = true;
cellsComplete++;
program.drawStatus(cellsComplete);
}
}
y++;
}
x++;
y = 0;
}
if (finished == false) {
int x2;
int y2;
onlyPossibilty = 0;
finished = false;
changedSomething = true;
while (finished == false && changedSomething == true) {
// System.out.println("Iteration");
x = 0;
y = 0;
finished = true;
changedSomething = false;
while (y < 9) {
while (x < 9) {
// System.out.println("X:" + x + " Y:" + y);
if (newCells[y][x] == 0) {
finished = false;
int values = 1;
while (values < 10) {
onlyPossibilty = 1;
// System.out.println("Y Checking " +
// values);
if (checkLegal(y, x, values, newCells) == true) {
// System.out.println(values +
// " can go here " + y + " " + x);
y2 = 0;
while (y2 < 9) {
if (y2 != y) {
if (checkLegal(y2, x, values, newCells) == true) {
onlyPossibilty = 0;
// System.out.println("Found another posibility "
// + y2 + " " + x);
y2 = 10;
}
}
y2++;
}
if (onlyPossibilty == 1) {
// System.out.println("Changed:" + y
// + " " + x + " to " + values +
// " Legal:" + checkLegal(y, x,
// values, newCells));
newCells[y][x] = values;
values = 10;
changedSomething = true;
cellsComplete++;
program.drawStatus(cellsComplete);
} else {
// System.out.println("X Checking "
// + values);
onlyPossibilty = 1;
x2 = 0;
while (x2 < 9) {
if (x2 != x) {
if (checkLegal(y, x2, values, newCells) == true) {
onlyPossibilty = 0;
// System.out.println("Found another posibility "
// + y + " " + x2);
x2 = 10;
}
}
x2++;
}
if (onlyPossibilty == 1) {
// System.out.println("Changed:"
// + y + " " + x + " to " +
// values + " Legal:" +
// checkLegal(y, x, values,
// newCells));
newCells[y][x] = values;
values = 10;
changedSomething = true;
cellsComplete++;
program.drawStatus(cellsComplete);
}
}
}
values++;
}
}
x++;
}
y++;
x = 0;
}
// System.out.println("End Iteration " + changedSomething);
}
}
}
if (cellsComplete == 81) {
return newCells;
} else {
program.drawStatus(0);
return null;
}
}
}
Chris