Блог

Я создаю решатель судоку, который пробует все возможные значения в квадрате и выполняет обратный отсчет, если это не приводит к решению. Я полагаю, что у меня есть почти рабочий алгоритм, но до сих пор он работал только над строками 0, 2 и 3 головоломки из 16 ячеек.

 public boolean fillBoard(int[][] board, int row, int col){
    int index = 1;              //Next value to try when an empty is found
    boolean solved = false;

    for(int i = row; i < width; i  ){       //For each row
        for(int j = col; j < height; j  ){  //For each column
            if(board[i][j]==0){             //0 represents empty
                while(!solved){
                    board[i][j] = index;
                    if(checker.checkRow(board[i]) 
                            amp;amp; checker.checkColumn(columnToArray(board, j))
                            //amp;amp; checker.checkBox(<input>)
                            ){
                            solved = fillBoard(board, i, 0);
                    }else{
                        if(index < width){
                            index  ;
                        }else{
                            return false;
                        }
                    }
                }
            }
        }
    }
    puzzle = copyPuzzle(board);
    return true;
}
  

Прямо сейчас он не проверяет третье правило судоку, он проверяет только столбцы и строки. Тем не менее, он все равно должен возвращать головоломку, которая соответствует правилам строк и столбцов, верно? И как только метод checkBox будет написан, он должен просто решить головоломку. Где я здесь напортачил?

ОТРЕДАКТИРУЙТЕ с помощью нескольких примеров:

Для ввода

         {1, 2, 0, 0},
        {0, 4, 0, 0},
        {0, 0, 1, 0},
        {0, 0, 3, 2}
  

Программа возвращает

1 2 4 3
4 4 4 4
2 3 1 4
4 1 3 2

Для ввода

         {1, 0},
        {2, 0}
  

Он решает это правильно.

Для ввода

         { 1, 0, 3, 4, 0, 0 },
        { 4, 0, 6, 0, 0, 3 },
        { 2, 0, 1, 0, 6, 0 },
        { 5, 0, 4, 2, 0, 0 },
        { 3, 0, 2, 0, 4, 0 },
        { 6, 0, 5, 0, 0, 2 }
  

Он возвращает неразрешенную головоломку

РЕДАКТИРОВАТЬ: checkRow для тех, кто спрашивал

 public boolean checkRow(int[]row){
    HashSet<Integer> set = new HashSet<Integer>();
    for(int i = 0; i < row.length;i  ){
        if(!set.add(row[i]) amp;amp; row[i]>0){//Duplicate?
            return false;
                    }
                }
    return true;
}
  

Проблема заключалась в том, что он не сбрасывал пробел на 0, когда значение было неправильным, поэтому, если он когда-либо достигал максимального индекса и был неправильным, он просто оставлял его. Приведенный ниже код работает. Просто жду, когда другой человек в моей группе предоставит метод проверки ящиков, но мне, вероятно, в конечном итоге придется делать это самому.

 public boolean fillBoard(int[][] board, int row, int col){
    int index = 1;              //Next value to try when an empty is found
    boolean solved = false;

    for(int i = row; i < width; i  ){       //For each row
        for(int j = col; j < height; j  ){  //For each column
            if(board[i][j]==0){             //0 represents empty
                while(!solved){             //While the puzzle is unsolved
                    board[i][j] = index;    //Try to fill with index
                    if(checker.checkRow(board[i]) 
                            amp;amp; checker.checkColumn(columnToArray(board, j))
                            //amp;amp; checker.checkBox(<input>)
                            ){
                            solved = fillBoard(board, i, 0); //Next space
                    }
                    if(!solved) board[i][j] = 0;
                    if(index < width){
                        index  ;
                    }else{
                        return false;
                    }                        
                }
            }
        }
    }
    puzzle = copyPuzzle(board);
    return true;
}