Language: Java
Aim: general: Solve a sudoku game
specific: Make a recursive method solve() that:
- Checks if number conflicts with other numbers in row, column or box
- Fills in integer between [1-9] in given empty space if that is not the case and move to next empty space
- (partially or fully) reverses progress if empty space can't be filled by integer between [1-9] without conflict. Then try again untill all empty spaces are filled (and sudoku is solved).
Problem: the loops try filling in integer n but will always try the lowest number first. If I were to use recursion the integers would always be the same.
Question: 1. How do you make code fill in numbers between and including 1 to 9.
How do you use recursion to partially or fully erase progress and try different numbers.
(extra) I've so far built code to solve a sudoku partially (until empty square can't be filled) but now it doesn't even fill in the first square even though it did earlier. It's not my main question but if anyone notices a/the issue, I would be very grateful if it were pointed out.
Reviewing: I'm reading course material on recursion but can't find the right information.
Disclaimer: All println commands outside of method printMatrix are for testing
Here's the method in question:
// prints all solutions that are extensions of current grid
// leaves grid in original state
void solve() {
//local variables
int[] currentSquare;
int currentRow;
int currentColumn;
boolean checkConflict;
currentSquare = new int[2];
//saftey limit for testing
int limit;
limit = 0;
while(findEmptySquare() != null){
currentSquare = findEmptySquare().clone();
currentRow = currentSquare[0];
currentColumn = currentSquare[1];
//System.out.println(" column c:"+currentColumn+" row r:"+currentRow); //column c5 r 3
if(currentSquare[0] != -1){
for(int n = 1; n <= ms; n++){
checkConflict = givesConflict(currentRow, currentColumn, n);
if(checkConflict == false){
grid[currentRow][currentColumn] = n;
}//end if
}//end for
}//end if
else{
System.out.println("solve: findEmptySquare was -1");
break;
}
//Safety limit
limit++;
if (limit > 20){
System.out.println("break");
break;
}//end if
}//end while
}
Here's the method that finds empty squares:
// finds the next empty square (in "reading order")
// returns array of first row then column coordinate
// if there is no empty square, returns .... (FILL IN!)
int[] findEmptySquare() {
int[] rowcol;
int[] noMoreCells;
rowcol = new int[2];
noMoreCells = new int[2];
noMoreCells[0] = -1;
noMoreCells[1] = -1;
for(int r = 0; r < ms; r++){
for(int c = 0; c < ms; c++){
if(grid[r][c] == 0){
if(r != rempty || c != cempty){ //check that the location of empty cell is not the same as last one
rempty = r;
cempty = c;
rowcol[0] = r; // 0 for row
rowcol[1] = c; // 1 for column
//System.out.println(" column c:"+rowcol[1]+" row r:"+rowcol[0]); //column c5 r 3
return rowcol;
}//end if
else{
System.out.println("findEmptySquare: found same empty square twice");
return noMoreCells;
}//end else
}//end if
}//end for
}//end for
System.out.println("findEmptySquare: no more empty cells");
return null; //no more empty cells
}
If necessary, the entire code (indentation is messy because I had to manually add spaces on stackoverflow):
// Alain Lifmann. Date: 26/9/2015
// Description of program: runs sudoku game
import java.util.*;
class Sudoku {
int ms = 9; //maze Size
int rempty; //keeping track of empty squares, row nr. (array)
int cempty; //keeping track of empty squares, column nr. (array)
int SIZE = 9; // size of the grid
int DMAX = 9; // maximal digit to be filled in
int BOXSIZE = 3; // size of the boxes
int[][] grid; // the puzzle grid; 0 represents empty
// a challenge-sudoku from the web
int[][] somesudoku = new int[][] {
{ 0, 6, 0, 0, 0, 1, 0, 9, 4 }, //original
// { 0, 0, 0, 0, 0, 1, 0, 9, 4 }, //to get more solutions
{ 3, 0, 0, 0, 0, 7, 1, 0, 0 },
{ 0, 0, 0, 0, 9, 0, 0, 0, 0 },
{ 7, 0, 6, 5, 0, 0, 2, 0, 9 },
{ 0, 3, 0, 0, 2, 0, 0, 6, 0 },
{ 9, 0, 2, 0, 0, 6, 3, 0, 1 },
{ 0, 0, 0, 0, 5, 0, 0, 0, 0 },
{ 0, 0, 7, 3, 0, 0, 0, 0, 2 },
{ 4, 1, 0, 7, 0, 0, 0, 8, 0 },
};
// a test-sudoku from oncourse
int[][] testsudoku = new int[][] {
{ 1, 2, 3, 4, 5, 6, 7, 8, 9 },
{ 4, 5, 6, 7, 8, 9, 1, 2, 3 },
{ 7, 8, 9, 1, 2, 3, 4, 5, 6 },
{ 2, 1, 4, 3, 6, 5, 8, 9, 7 },
{ 3, 6, 5, 8, 9, 7, 2, 1, 4 },
{ 8, 9, 7, 2, 1, 4, 3, 6, 5 },
{ 5, 3, 1, 6, 4, 2, 9, 7, 8 },
{ 6, 4, 2, 9, 7, 8, 5, 3, 1 },
{ 9, 7, 8, 5, 3, 1, 6, 4, 2 },
};
// a test-sudoku modified to be incomplete
int[][] testsudoku2 = new int[][] {
{ 0, 0, 3, 0, 5, 6, 7, 8, 0 },
{ 0, 5, 0, 7, 0, 0, 1, 0, 3 },
{ 7, 0, 0, 1, 0, 3, 4, 5, 6 },
{ 2, 1, 4, 3, 6, 5, 8, 0, 7 },
{ 3, 0, 5, 8, 0, 7, 0, 1, 0 },
{ 0, 9, 7, 0, 1, 4, 3, 0, 5 },
{ 0, 0, 0, 6, 4, 2, 9, 7, 8 },
{ 0, 4, 2, 9, 7, 8, 0, 0, 1 },
{ 0, 0, 0, 5, 3, 1, 0, 4, 0 },
};
int solutionnr = 0; //solution counter
// ----------------- conflict calculation --------------------
// is there a conflict when we fill in d at position r,c?
boolean givesConflict(int r, int c, int d) {
if(rowConflict(r, d) == true){
return true;
}//end if
if(colConflict(c, d) == true){
return true;
}//end if
if(boxConflict(r, c, d) == true){
return true;
}//end if
return false;
}//end givesConflict
boolean rowConflict(int r, int d) {
for(int i = 0; i < ms; i++){
if(d == grid[r][i]){
//System.out.println("rowconflict r:"+r+" d:"+d);
return true;
}//end if
}//end for
return false; //no conflict
}
boolean colConflict(int c, int d) {
for(int i = 0; i < ms; i++){
if(d == grid[i][c]){
//System.out.println("column conflict c:"+c+" d:"+d);
return true;
}//end if
}//end for
return false; //no conflict
}
boolean boxConflict(int rr, int cc, int d) { //test 5,3,1
int rs; // Box-row start point
int cs; // Box-column start point
rs = rr - rr%3;
cs = cc - cc%3;
//System.out.println("box start is row "+rs+" , column "+cs);
for(int r = rs; r < rs + 3; r++ ){
for(int c = cs; c < cs + 3; c++){
if(d == grid[r][c]){
//System.out.println("r:"+r+" c:"+c);
return true;
}//end if
}//end for
}//end for
return false; //no conflict
}
// --------- solving ----------
// finds the next empty square (in "reading order")
// returns array of first row then column coordinate
// if there is no empty square, returns .... (FILL IN!)
int[] findEmptySquare() {
int[] rowcol;
int[] noMoreCells;
rowcol = new int[2];
noMoreCells = new int[2];
noMoreCells[0] = -1;
noMoreCells[1] = -1;
for(int r = 0; r < ms; r++){
for(int c = 0; c < ms; c++){
if(grid[r][c] == 0){
if(r != rempty || c != cempty){ //check that the location of empty cell is not the same as last one
rempty = r;
cempty = c;
rowcol[0] = r; // 0 for row
rowcol[1] = c; // 1 for column
//System.out.println(" column c:"+rowcol[1]+" row r:"+rowcol[0]); //column c5 r 3
return rowcol;
}//end if
else{
System.out.println("findEmptySquare: found same empty square twice");
return noMoreCells;
}//end else
}//end if
}//end for
}//end for
System.out.println("findEmptySquare: no more empty cells");
return null; //no more empty cells
}
// prints all solutions that are extensions of current
// leaves grid in original state
void solve() {
//local variables
int[] currentSquare;
int currentRow;
int currentColumn;
boolean checkConflict;
currentSquare = new int[2];
//saftey limit for testing
int limit;
limit = 0;
while(findEmptySquare() != null){
currentSquare = findEmptySquare().clone();
currentRow = currentSquare[0];
currentColumn = currentSquare[1];
//System.out.println(" column c:"+currentColumn+" row r:"+currentRow); //column c5 r 3
if(currentSquare[0] != -1){
for(int n = 1; n <= ms; n++){
checkConflict = givesConflict(currentRow, currentColumn, n);
if(checkConflict == false){
grid[currentRow][currentColumn] = n;
}//end if
}//end for
}//end if
else{
System.out.println("solve: findEmptySquare was -1");
break;
}
//Safety limit
limit++;
if (limit > 20){
System.out.println("break");
break;
}//end if
}//end while
}
// ------------------------- misc -------------------------
// print the grid, 0s are printed as spaces
void printMatrix(){
int ms; //matrix Size
ms = 9;
//layer indication symbols
String end;
String mid;
String cut;
end = "+";
mid = "-";
cut = "";
for(int i = 0; i < 2*ms-1; i++){
cut = cut + mid;
}//end for
System.out.println(end+cut+end);
for(int i = 0; i < ms; i++){
if( i % 3 == 0 && i != 0){
System.out.println(mid+cut+mid);
}//end if
for(int j = 0; j < ms; j++){
if( j % 3 == 0){
System.out.print("|");
}//end if
else{
System.out.print(" ");
}//end else
if(grid[i][j] != 0){
System.out.print(grid[i][j]);
}//end if
else{
System.out.print(" ");
}//end else
}//end for j
System.out.print("|");
System.out.println();
}//end for i
System.out.println(end+cut+end);
}//end method
// reads the initial grid from stdin
void read() {
Scanner sc = new Scanner(System.in);
for (int r=0; r<SIZE; r++) {
if (r % BOXSIZE == 0) {
sc.nextLine(); // read away top border of box
}
for (int c=0; c < SIZE; c++) {
if (c % BOXSIZE == 0) {
sc.next(); // read away left border of box
}
String square = sc.next();
if (".".equals(square)) {
grid[r][c] = 0; // empty sqaure
} else {
grid[r][c] = Integer.parseInt(square);
}
//System.out.print(grid[r][c]);
}
sc.nextLine(); // read away right border
}
sc.nextLine(); // read away bottom border
}
// --------------- where it all starts --------------------
void solveIt() {
grid = somesudoku.clone(); // set used grid (before doing anything else)
printMatrix();
solve();
printMatrix();
/* test material
printMatrix();
//System.out.println(givesconflict(1,1,3));
System.out.println(rowConflict(0,1));
System.out.println(colConflict(0,1));
System.out.println(boxConflict(0,0,1));
findEmptySquare();
*/
}// end solveIt
public static void main(String[] args) {
new Sudoku().solveIt();
}
}
