Итеративная грубая сила sudoku solver

Question

Я пытаюсь реализовать итеративный решатель Судоку. Чтобы избежать рекурсии, я использовал стек, но у меня проблемы с его управлением. Начальная плата представлена ​​массивом String (переменная «input» в следующем коде), в которой каждый элемент состоит из трех чисел: [строка, col] и его значение (то есть «006» означает, что элемент в 1-я строка и 1-й столбец 6) и преобразуется в массив int конструктором. Когда я запускаю его, я не могу получить решение, поэтому, возможно, ошибки вложенных циклов. Любая помощь приветствуется.

import java.util.ArrayList; 

public class SudokuSolver { 

    private int[][] matrix = new int[9][9]; 
    private String[] input = { "006", "073", "102", "131", "149", "217", 
     "235", "303", "345", "361", "378", "422", "465", "514", "521", 
     "548", "582", "658", "679", "743", "752", "784", "818", "883" }; 

    private ArrayList<int[][]> stack = new ArrayList<>(); 

    public SudokuSolver() { 
     // Building the board based on input array 
     for (int n = 0; n < input.length; ++n) { 
      int i = Integer.parseInt(input[n].substring(0, 1)); 
      int j = Integer.parseInt(input[n].substring(1, 2)); 
      int val = Integer.parseInt(input[n].substring(2, 3)); 
      matrix[i][j] = val; 
     } 
     stack.add(matrix); 
    } 

    private boolean isSolution(int[][] cells) { 
     for (int i = 0; i < 9; i++) { 
      for (int j = 0; j < 9; j++) { 
       if(cells[i][j] == 0) 
        return false; 
      } 
     } 
     return true; 
    } 

    private boolean isValid(int i, int j, int val, int[][] cells) { 
     for (int k = 0; k < 9; k++) 
      if (val == cells[k][j]) 
       return false; 
     for (int k = 0; k < 9; k++) 
      if (val == cells[i][k]) 
       return false; 
     return true; 
    } 

    private boolean iterativeSudokuSolver() { 
     int[][] current = null; 

     while(stack.size() > 0 && !isSolution(stack.get(0))) { 
      current = stack.remove(0); 

      for (int row = 0; row < 9; row++) { 
       for (int col = 0; col < 9; col++) { 
        if (current[row][col] == 0) { 
         for (int val = 1; val <= 9; val++) { 
          if (isValid(row, col, val, current)) { 
           current[row][col] = val; 
           stack.add(0, current); 
           break; 
          } 
         } 
        } 
       } 
      } 
     } 
     if (current != null && isSolution(current)) 
      return true; 
     else 
      return false; 
    } 

    public static void main(String [] args) { 
     SudokuSolver sudokuSolver = new SudokuSolver(); 
     boolean result = sudokuSolver.iterativeSudokuSolver(); 

     if (result) 
      System.out.println("Sudoku solved"); 
     else 
      System.out.println("Sudoku not solved"); 
    } 
} 

Answer 1

1. Реализация стека путем добавления и удаления 0-й элемент в ArrayList очень плохая идея: она заставляет все содержимое массива должен быть сдвинут назад в вперед каждый раз. Используйте LinkedList или измените конец списка.
2. Когда вы добавляете и удаляете один и тот же экземпляр матрицы назад и вперед в стек, это все тот же объект матрицы, даже если вы можете назвать его «текущим» или любым другим именем. Это означает, что когда вы меняете что-то в матрице, а затем удаляете ее из своего стека, изменение остается там (и в каждом другом элементе вашего стека, которые являются идентичными ссылками на один и тот же объект). Логика вашего решения выглядит так, что ему нужно сохранить предыдущее состояние решения в стеке, если это так - каждый раз выделять новый массив и копировать данные (также не очень эффективно, но попробуйте начать с него).
3. Хороший вопрос должен быть конкретным. «Почему это не работает?» это плохой вопрос. Сначала устраните очевидные проблемы, отлаживайте и, если они озадачены, предоставите дополнительную информацию о состоянии вашей программы (данные, например, данные на шаге № 1 ... N)