Вилка/Регистрация Судоку Solver

Question

У меня проблема с упражнением. Мне нужно найти все решения для данной судоку, используя параллелизм fork/join. Я сделал алгоритм, но, похоже, он не работает. В какой-то момент это останавливается, и я не могу понять, почему.

Вот код:

private static int counter; 
private Cella[][] sudoku; 
private int i; 
private int j; 
private int theCounter = 0; 

public SudokuMulti(Cella[][] sudoku) { 
    this.sudoku = sudoku; 
} 

public SudokuMulti(Cella[][] sudoku, int i, int j) { 
    this.sudoku = sudoku; 
    this.i = i; 
    this.j = j; 
} 

//DELETED 

// Copy the sudoku matrix 
private Cella[][] createCopy() { 
    Cella[][] toReturn = new Cella[9][9]; 
    for (int i = 0; i < 9; i++) { 
     System.arraycopy(sudoku[i], 0, toReturn[i], 0, 9); 
    } 
    return toReturn; 
} 

И код объекта Cella:

public class Cella { 

private int current; 

public Cella() { 
    current = 0; 
} 

public Cella(int current) { 
    this.current = current; 
} 

//Getter and Setter 

Моя идея заключается в том, чтобы дать каждому потоку факультет, чтобы решить свою собственную судоку, учитывая «правовой значения "ячейки-кандидата. Затем я собираю все потоки в ArrayList и прошу их использовать fork с последним. Каждый поток должен возвращать Integer (0 без успеха, 1 для успеха), чтобы подсчитать, сколько возможных судокумов можно решить.

Однако алгоритм охватывает только 1/3 судоку: после определенного момента он перестает заполнять ячейки, и он просто возвращается, не завершая его.

Может ли кто-нибудь предложить мне, где я совершаю ошибку (ы)?

Answer 1

Я нашел решение. Здесь ошибка:

// Copy the sudoku matrix 
private Cella[][] createCopy() { 
    Cella[][] toReturn = new Cella[9][9]; 
    for (int i = 0; i < 9; i++) { 
     // !!ERROR!! 
     System.arraycopy(sudoku[i], 0, toReturn[i], 0, 9); 
    } 
    return toReturn; 
} 

Когда я скопировать массив я заполнить его с ссылкой на объект Cella и не новое, поэтому он вызывает скачки данных.

Правильный способ для копирования матрицы является:

private Cella[][] createCopy() { 
    Cella[][] toReturn = new Cella[9][9]; 
    for (int i = 0; i < 9; i++) { 
     for (int j = 0; j < 9; j++) { 
      toReturn[i][j] = new Cella(sudoku[i][j].getCurrent()); 
     } 
    } 
    return toReturn; 
} 

Answer 2

Из какого кода вы опубликовали сообщение, я не вижу проблемы, которая объясняет вашу проблему. Тем не менее, вы не опубликовали код, который я могу скомпилировать и выполнить самостоятельно (известный как минимальный рабочий или проверяемый пример, см. Wikipedia и StackOverflow's guide on creating one), и вы не опубликовали трассировку стека или вывод для своего приложения. Это затрудняет вам помощь в решении вашей проблемы. Если вы можете предоставить мне больше, я готов продолжать помогать вам в решении вашей проблемы.

Тем временем я попытался свернуть программу, которая решает ту же проблему после вашего подхода. Кажется, что это работает, хотя я не полностью его протестировал. Возможно, вы можете сравнить его с тем, что вы написали, и использовать различия, чтобы обнаружить проблему. Для компиляции и запуска этого кода вам понадобится хотя бы Java 7.

Если это для домашнего задания, я рекомендую проверить его с вашим профессором или ТП, прежде чем смотреть на это объявление.

public class Main { 
    public static void main(String[] args) { 
     Sudoku puzzle = new Sudoku(); 
      // Uncomment these lines to have a uniquely solvable Sudoku puzzle. They are commented out to prove that this code can count multiple solutions. 
//  puzzle.set(1, 0, 2); 
//  puzzle.set(2, 0, 9); 
//  puzzle.set(4, 0, 5); 
//  puzzle.set(7, 0, 4); 
//  puzzle.set(8, 0, 1); 
//  puzzle.set(3, 1, 8); 
//  puzzle.set(6, 1, 3); 
//  puzzle.set(2, 2, 3); 
     puzzle.set(3, 2, 7); 
     puzzle.set(4, 2, 4); 
     puzzle.set(5, 2, 9); 
     puzzle.set(6, 2, 6); 
     puzzle.set(3, 3, 4); 
     puzzle.set(6, 3, 2); 
     puzzle.set(7, 3, 1); 
     puzzle.set(1, 4, 6); 
     puzzle.set(3, 4, 3); 
     puzzle.set(4, 4, 7); 
     puzzle.set(5, 4, 1); 
     puzzle.set(7, 4, 8); 
     puzzle.set(1, 5, 4); 
     puzzle.set(2, 5, 1); 
     puzzle.set(5, 5, 6); 
     puzzle.set(2, 6, 5); 
     puzzle.set(3, 6, 9); 
     puzzle.set(4, 6, 2); 
     puzzle.set(5, 6, 8); 
     puzzle.set(6, 6, 7); 
     puzzle.set(2, 7, 4); 
     puzzle.set(5, 7, 7); 
     puzzle.set(0, 8, 3); 
     puzzle.set(1, 8, 7); 
     puzzle.set(4, 8, 6); 
     puzzle.set(6, 8, 5); 
     puzzle.set(7, 8, 2); 

     SudokuSolver solver = new SudokuSolver(puzzle); 
     long start = System.nanoTime(); 
     int totalSolutions = solver.compute(); 
     long end = System.nanoTime(); 
     System.out.println(totalSolutions); 
     System.out.format("%f ms", (end - start)/1e6); 
    } 

    private static class Sudoku { 
     private final int[][] cells; 

     Sudoku() { 
      cells = new int[9][9]; 
     } 

     Sudoku(Sudoku original) { 
      cells = new int[9][9]; 
      for (int column = 0; column < 9; ++column) { 
       for (int row = 0; row < 9; ++row) { 
        set(column, row, original.get(column, row)); 
       } 
      } 
     } 

     int get(int column, int row) { 
      return cells[column][row]; 
     } 

     void set(int column, int row, int value) { 
      cells[column][row] = value; 
     } 

     boolean isPlausible() { 
      return columnsArePlausible() && rowsArePlausible() && blocksArePlausible(); 
     } 

     private boolean columnsArePlausible() { 
      boolean result = true; 

      for (int column = 0; result && column < 9; ++column) { 
       result = isColumnPlausible(column); 
      } 

      return result; 
     } 

     private boolean isColumnPlausible(int column) { 
      boolean result = true; 

      boolean[] seen = new boolean[10]; 
      for (int row = 0; result && row < 9; ++row) { 
       int value = get(column, row); 
       if (value > 0 && seen[value]) { 
        result = false; 
       } else { 
        seen[value] = true; 
       } 
      } 

      return result; 
     } 

     private boolean rowsArePlausible() { 
      boolean result = true; 

      for (int row = 0; result && row < 9; ++row) { 
       result = isRowPlausible(row); 
      } 

      return result; 
     } 

     private boolean isRowPlausible(int row) { 
      boolean result = true; 

      boolean[] seen = new boolean[10]; 
      for (int column = 0; result && column < 9; ++column) { 
       int value = get(column, row); 
       if (value > 0 && seen[value]) { 
        result = false; 
       } else { 
        seen[value] = true; 
       } 
      } 

      return result; 
     } 

     private boolean blocksArePlausible() { 
      boolean result = true; 

      for (int column = 0; result && column < 9; column += 3) { 
       for (int row = 0; result && row < 9; row += 3) { 
        result = isBlockPlausible(column, row); 
       } 
      } 

      return result; 
     } 

     private boolean isBlockPlausible(int column, int row) { 
      boolean result = true; 

      boolean[] seen = new boolean[10]; 
      for (int x = 0; result && x < 3; ++x) { 
       for (int y = 0; result && y < 3; ++y) { 
        int value = get(column + x, row + y); 
        if (value > 0 && seen[value]) { 
         result = false; 
        } else { 
         seen[value] = true; 
        } 
       } 
      } 

      return result; 
     } 
    } 

    private static class SudokuSolver extends RecursiveTask<Integer> { 
     private static final long serialVersionUID = 8759452522630056046L; 

     private Sudoku state; 
     private int column; 
     private int row; 

     SudokuSolver(Sudoku state) { 
      this.state = state; 
      // These settings allow the search loop in compute() to increment first without asking questions about 
      // whether this cell has been checked yet. 
      column = -1; 
      row = 8; 
     } 

     SudokuSolver(Sudoku state, int column, int row) { 
      this.column = column; 
      this.row = row; 
      this.state = state; 
     } 

     @Override 
     protected Integer compute() { 
      int viableSolutions = 0; 

      if (state.isPlausible()) { 
       int originalColumn = column; 
       int originalRow = row; 

       do { 
        if (row + 1 >= 9) { 
         ++column; 
         row = 0; 
        } else { 
         ++row; 
        } 
       } while (column < 9 && state.get(column, row) != 0); 

       if (column >= 9) { 
        viableSolutions = 1; 
       } else { 
        List<SudokuSolver> solvers = new ArrayList<>(); 
        for (int value = 1; value <= 9; ++value) { 
         Sudoku copy = new Sudoku(state); 
         copy.set(column, row, value); 
         solvers.add(new SudokuSolver(copy, column, row)); 
        } 
        invokeAll(solvers); 
        for (SudokuSolver solver : solvers) { 
         viableSolutions += solver.join(); 
        } 
       } 
      } 

      return viableSolutions; 
     } 
    } 
} 

Поскольку этот код раз, сколько времени требуется, чтобы рассчитывать решения, выход может меняться, но я получил

354 
709.848410 ms