Sudoku

Question

I don’t know what I am doing wrong, and I have been looking at this code all day. This is the "standard" Sudoku solver in Java, which takes int[][] from 0, where the empty spaces are. Given that I only go on a 35-hole board, this should solve most problems, but only 66% can solve it. Otherwise, there are several (usually 2 or 4) empty spaces that cannot be resolved (i.e. the Wrong number was written to the board ). Almost always it will be 9 that are missing.

I understand that such a simple solution will not solve all of sudoku. I intentionally give him the lungs.

 import java.util.ArrayList; import java.util.List; public class SudokuSolver { public SudokuSolver() { init(); } public boolean solve() { /* Each method checks (in different ways) to see if it can find a new number If said method does find a number, it sets off a chain reaction, starting back at the beginning. */ int countdown = 20; while(!solved() && --countdown > 0) { if(given()) continue; if(findSingletons()) continue; if(zerosLeft() <= 4) justGuess(); } return solved(); } public boolean given() { boolean repeat = false; //Iterate through every given number for(int i=0;i<9;i++) { for(int j=0;j<9;j++) { if(board[i][j] != 0 && !found[i][j]) { repeat = true; foundNum(i, j, board[i][j]); } } } //Call given every time a new number is found return repeat; } public boolean findSingletons() { boolean repeat = false; //LOTS of iteration, but I'm out of ideas. int[] values; ArrayList<Integer> singletons = new ArrayList<Integer>(); for(int i=0;i<9;i++) { values = new int[10]; singletons.clear(); for(int j=0;j<9;j++) for(int k=0;k<possible[i][j].size();k++) values[possible[i][j].get(k)]++; for(int j=1;j<10;j++) if(values[j] == 1) singletons.add(j); for(int j=0;j<9;j++) for(int k=0;k<singletons.size();k++) if(possible[i][j].contains(singletons.get(k))) { foundNum(i, j, singletons.get(k)); repeat = true; } } for(int i=0;i<9;i++) { values = new int[10]; singletons.clear(); for(int j=0;j<9;j++) for(int k=0;k<possible[j][i].size();k++) values[possible[j][i].get(k)]++; for(int j=1;j<10;j++) if(values[j] == 1) singletons.add(j); for(int j=0;j<9;j++) for(int k=0;k<singletons.size();k++) if(possible[j][i].contains(singletons.get(k))) { foundNum(j, i, singletons.get(k)); repeat = true; } } int[] corners = {0,3,6}; for(int a=0;a<3;a++) for(int l=0;l<3;l++) for(int i=corners[a];i<corners[a]+3;i++) { values = new int[10]; singletons.clear(); for(int j=corners[l];j<corners[l]+3;j++) for(int k=0;k<possible[i][j].size();k++) values[possible[i][j].get(k)]++; for(int j=1;j<10;j++) if(values[j] == 1) singletons.add(j); for(int j=0;j<9;j++) for(int k=0;k<singletons.size();k++) if(possible[i][j].contains(singletons.get(k))) { foundNum(i, j, singletons.get(k)); repeat = true; } } return repeat; } public void justGuess() { outer: for(int i=0;i<9;i++) for(int j=0;j<9;j++) if(board[i][j] == 0) { foundNum(i, j, possible[i][j].get(0)); break outer; } } public void foundNum(int x, int y, int numFound) { if(board[x][y] != 0 && board[x][y] != numFound) { throw new RuntimeException("Attempting to place a number where one was already found"); } board[x][y] = numFound; possible[x][y].clear(); possible[x][y].add(numFound); found[x][y] = true; for(int i=0;i<9;i++) { if(i != x) if(possible[i][y].indexOf(numFound) != -1) possible[i][y].remove(possible[i][y].indexOf(numFound)); } for(int i=0;i<9;i++) { if(i != y) if(possible[x][i].indexOf(numFound) != -1) possible[x][i].remove(possible[x][i].indexOf(numFound)); } int cornerX = 0; int cornerY = 0; if(x > 2) if(x > 5) cornerX = 6; else cornerX = 3; if(y > 2) if(y > 5) cornerY = 6; else cornerY = 3; for(int i=cornerX;i<10 && i<cornerX+3;i++) for(int j=cornerY;j<10 && j<cornerY+3;j++) if(i != x && j != y) if(possible[i][j].indexOf(numFound) != -1) possible[i][j].remove(possible[i][j].indexOf(numFound)); } public boolean solved() { for(int i=0;i<9;i++) for(int j=0;j<9;j++) if(!found[i][j]) return false; return true; } public void reset(int[][] board) { this.board = board; init(); } public void init() { possible = new ArrayList[9][9]; for(int i=0;i<9;i++) for(int j=0;j<9;j++) { possible[i][j] = new ArrayList<Integer>(); for(int k=1;k<10;k++) possible[i][j].add(k); } found = new boolean[9][9]; } public void print() { for(int i=0;i<9;i++) { if(i%3==0 && i != 0) System.out.println("- - - | - - - | - - -"); for(int j=0;j<9;j++) { if(j%3==0 & j != 0) System.out.print("| "); System.out.print(board[i][j] + " "); } System.out.println(); } System.out.println(); } private int zerosLeft() { int empty = 0; for(int i=0;i<9;i++) for(int j=0;j<9;j++) if(board[i][j] == 0) empty++; return empty; } private void data(int difficulty) { int empty = 0; for(int i=0;i<9;i++) for(int j=0;j<9;j++) if(board[i][j] == 0) empty++; System.out.println(empty); } public static void main(String[] args) { SudokuGenerator sg = new SudokuGenerator(); SudokuSolver ss = new SudokuSolver(); int[][] tempBoard = {{4, 0, 1, 0, 9, 7, 0, 5, 8 }, {2, 0, 0, 5, 3, 1, 4, 0, 6 }, {5, 0, 6, 4, 0, 2, 0, 3, 9 }, {0, 9, 0, 0, 0, 4, 3, 0, 2 }, {0, 0, 0, 9, 0, 0, 6, 4, 7 }, {7, 0, 4, 0, 0, 0, 9, 0, 5 }, {0, 0, 7, 0, 0, 3, 8, 9, 4 }, {8, 5, 0, 1, 4, 9, 7, 0, 0 }, {9, 0, 3, 8, 7, 6, 0, 0, 0 }}; ss.reset(tempBoard); System.out.println(ss.solve()); ss.print(); ss.data(35); } int[][] board; ArrayList<Integer>[][] possible; boolean[][] found; } 

I am still new to programming, so any advice other than resolving this would be welcome. (Especially optimize possible . This is the most profane code I've written to date.)

Thanks!

Answer 1

I started reading your code, but it feels longer than it should be, and these loops get pretty dirty. Nothing jumps at me immediately. You said that you do not just want solutions, but also tips.

You should find out if there is a problem with your design (it does not work for Sudoku solution), or if there is just an error in the implementation. Perhaps read and write comments on what each loop does, the “rubber duck test”, as a result of which you are forced to explain everything, you will stop yourself and realize that something is not needed, or it is not what it should be. This helps with design issues.

If the problem is implementation, do you know how to formally debug an application? Set breakpoints and go through the instructions according to the instructions? If you have a small mistake, but you don’t see where to go. Find a really simple example that fails, then run this test and break it at the beginning. Step by step and follow the logic. I hope you see where this is happening. Writing JUnit tests or log statements is great, but when you have a tricky error, you have to make a real debug breakpoint.

Your general structure is good, you have some objects for storing data and a good cleaning method that calls several different methods and passes through them. But each of these methods, wow, they are sure that they are dirty. This type of code, many hard loops using the same variable names, a lot of manipulation with arrays, breaks something so easily and gets an error, and this makes reading and detecting errors difficult.

Eclipse makes it easy to debug java if you haven’t done this before. A lot of good tutorials on google, so I won’t worry ^ _ ~

Answer 2

It seems you are not implementing a return mechanism. In some cases, you need to guess the numbers if you do not have the correct heuristic.

Heuristics are "trading tricks", here is a list of common Sudoku .

If you only programmed a few of them, you will end up in dead ends and will have to guess. This complicates the task, because you have to consider that these guesses may be wrong. Backtracking is a strategy that allows you to “roll back” a few guesses and make different ones. Think of it as a tree of opportunity to make some brute force to solve sudoku.

So, your 2 options - implement more heuristics or find a way to make a wider range of guesses