Language: Java
Purpose: General: Solve sudoku game.
specific: Make a recursive solve () method that:
- Checks if a number conflicts with other numbers in a row, column or field
- Fills an integer between [1-9] in the given empty space, if this is not the case and move to the next empty space
- (partially or completely) cancels the progress if the empty space cannot be filled with an integer between [1-9] without conflict. Then try again until all empty spaces are full (and sudoku is allowed).
Problem: The loops will try to fill the integer n, but will always try to execute the lowest number. If I used recursion, integers would always be the same.
Question: 1. How do you make the code, filling in the numbers between 1 and 9 and including.
How do you use recursion to partially or completely remove progress and try different numbers.
(optional) I have still created the code for partially solving Sudoku (until the empty square cannot be filled), but now it does not even fill the first square, even if he did it before. This is not my main question, but if anyone notices the question /, I would be very grateful if that were indicated.
Reviewing: I read recursion course material but cannot find the information I need.
Disclaimer: All println commands outside the printMatrix method are for testing purposes.
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 is a 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, all the code (the indentation is dirty, because I had to manually add spaces in 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(); } }