Java – recursion: how to try different combinations of integers 1 to 9 and (partially) reverse sequences to restart in case of error?
•
Java
Language:
Goal: General: solve a Sudoku game
Specifically: make a recursive method, solve ():
>Check whether the number conflicts with other numbers in the row, column or box > if not, fill the given blank space with integers between [1-9], and then move to the next blank area > (part or all) if the space cannot be filled with integers between [1-9] without conflict, the progress will be reversed Then try again until all the spaces are filled (and Sudoku is solved)
Problem: the loop tries to fill in the integer n, but always tries the smallest number first If I use recursion, integers will always be the same
Question: 1 How to make the code fill in numbers between 1 and 9
>How to use recursion to partially or completely erase progress and try different numbers. > (extra) I've built code so far to partially solve Sudoku (until the empty box can't be filled), but now it doesn't even fill the first box, even if it's done before This is not my main problem, but I would appreciate it if anyone noticed it, if anyone pointed it out
Review: I'm reading the course material on recursion, but I can't find the right information
Disclaimer: all println commands other than the method printmatrix are used for testing
This is the problematic approach:
// 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
}
This is how to find an empty box:
// 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 (the indentation is cluttered because I have to manually add spaces on stack overflow):
// 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 @R_440_2419@SIZE = 3; // size of the @R_440_2419@es
int[][] grid; // the puzzle grid; 0 represents empty
// a challenge-sudoku from the web
int[][] somesudoku = new int[][] {
{ 0,6,1,9,4 },//original
// { 0,//to get more solutions
{ 3,7,0 },{ 0,{ 7,5,2,9 },3,{ 9,1 },2 },{ 4,8,};
// a test-sudoku from oncourse
int[][] testsudoku = new int[][] {
{ 1,4,3 },6 },{ 2,7 },{ 3,{ 8,5 },{ 5,8 },{ 6,};
// a test-sudoku modified to be incomplete
int[][] testsudoku2 = new int[][] {
{ 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(@R_440_2419@Conflict(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 @R_440_2419@Conflict(int rr,int cc,int d) { //test 5,1
int rs; // @R_440_2419@-row start point
int cs; // @R_440_2419@-column start point
rs = rr - rr%3;
cs = cc - cc%3;
//System.out.println("@R_440_2419@ 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,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 % @R_440_2419@SIZE == 0) {
sc.nextLine(); // read away top border of @R_440_2419@
}
for (int c=0; c < SIZE; c++) {
if (c % @R_440_2419@SIZE == 0) {
sc.next(); // read away left border of @R_440_2419@
}
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,3));
System.out.println(rowConflict(0,1));
System.out.println(colConflict(0,1));
System.out.println(@R_440_2419@Conflict(0,1));
findEmptySquare();
*/
}// end solveIt
public static void main(String[] args) {
new Sudoku().solveIt();
}
}
Solution
This problem can be solved by backtracking You must recurse through all possible options, but when you encounter an incorrect problem, please return from this path
The content of this article comes from the network collection of netizens. It is used as a learning reference. The copyright belongs to the original author.
THE END
二维码