Java - Sudoku (backtracking) 'is place valid' метод необходимо.

Question

У меня этот код Судоку, который выполняется с помощью обратного отслеживания, и я все понимаю, кроме нескольких строк кода, которые я прошу объяснить. Это весь код.

public class Sudoku { 


    static int N = 9; 


    static int grid[][] = { { 3, 0, 6, 5, 0, 8, 4, 0, 0 }, 
      { 5, 2, 0, 0, 0, 0, 0, 0, 0 }, 
      { 0, 8, 7, 0, 0, 0, 0, 3, 1 }, 
      { 0, 0, 3, 0, 1, 0, 0, 8, 0 }, 
      { 9, 0, 0, 8, 6, 3, 0, 0, 5 }, 
      { 0, 5, 0, 0, 9, 0, 6, 0, 0 }, 
      { 1, 3, 0, 0, 0, 0, 2, 5, 0 }, 
      { 0, 0, 0, 0, 0, 0, 0, 7, 4 }, 
      { 0, 0, 5, 2, 0, 6, 3, 0, 0 } }; 

    static class Cell { 

     int row, col; 

     public Cell(int row, int col) { 
      super(); 
      this.row = row; 
      this.col = col; 
     } 

     @Override 
     public String toString() { 
      return "Cell [row=" + row + ", col=" + col + "]"; 
     } 
    }; 



    static boolean isValid(Cell cell, int value) { 

     if (grid[cell.row][cell.col] != 0) { 
      throw new RuntimeException("Cannot call for cell which already has a value"); 
     } 


     for (int c = 0; c < 9; c++) { 
      if (grid[cell.row][c] == value) 
       return false; 
     } 


     for (int r = 0; r < 9; r++) { 
      if (grid[r][cell.col] == value) 
       return false; 
     } 


     int x1 = 3 * (cell.row/3); 
     int y1 = 3 * (cell.col/3); 
     int x2 = x1 + 2; 
     int y2 = y1 + 2; 

     for (int x = x1; x <= x2; x++) 
      for (int y = y1; y <= y2; y++) 
       if (grid[x][y] == value) 
        return false; 

     return true; 
    } 


    static Cell getNextCell(Cell cur) { 

     int row = cur.row; 
     int col = cur.col; 


     col++; 

     if (col > 8) { 

      col = 0; 
      row++; 
     } 


     if (row > 8) 
      return null; 

     Cell next = new Cell(row, col); 
     return next; 
    } 


    static boolean solve(Cell cur) { 


     if (cur == null) 
      return true; 


     if (grid[cur.row][cur.col] != 0) { 

      return solve(getNextCell(cur)); 
     } 


     for (int i = 1; i <= 9; i++) { 

      boolean valid = isValid(cur, i); 

      if (!valid) 
       continue; 


      grid[cur.row][cur.col] = i; 


      boolean solved = solve(getNextCell(cur)); 

      if (solved) 
       return true; 
      else 
       grid[cur.row][cur.col] = 0; 

     } 

     return false; 
    } 

    public static void main(String[] args) { 
     boolean solved = solve(new Cell(0, 0)); 
     if (!solved) { 
      System.out.println("SUDOKU cannot be solved."); 
      return; 
     } 
     System.out.println("SOLUTION\n"); 
     printGrid(grid); 
    } 


    static void printGrid(int grid[][]) { 
     for (int row = 0; row < N; row++) { 
      for (int col = 0; col < N; col++) 
       System.out.print(grid[row][col]); 
      System.out.println(); 
     } 
    } 
} 

Однако, если вы идете в isValid метод, который я действительно не могу понять эту часть. Если кто-то может подробно объяснить эту часть и что именно она делает, это было бы здорово. Я видел это во многих кодах, но я до сих пор не могу понять.

 int x1 = 3 * (cell.row/3); 
     int y1 = 3 * (cell.col/3); 
     int x2 = x1 + 2; 
     int y2 = y1 + 2; 

     for (int x = x1; x <= x2; x++) 
      for (int y = y1; y <= y2; y++) 
       if (grid[x][y] == value) 
        return false; 

     return true; 

Answer 1

 int x1 = 3 * (cell.row/3); 
     int y1 = 3 * (cell.col/3); 
     int x2 = x1 + 2; 
     int y2 = y1 + 2; 

     for (int x = x1; x <= x2; x++) 
      for (int y = y1; y <= y2; y++) 
       if (grid[x][y] == value) 
        return false; 

     return true; 

Этот блок кода содержит поле 3x3, содержащее текущий номер. Вложенные циклы проверяют, что данное число не существует в поле 3x3.

---

Если вы задаетесь вопросом, почему формула (разделить на 3 затем умножить на 3), а затем путем добавления 2. Посмотрите:

Если текущая строка 0..8:

3 * (0/3) + 2 = 2 (read 3x3 box starting from pos 0 to 2) 
3 * (1/3) + 2 = 2 (read 3x3 box starting from pos 0 to 2) 
3 * (2/3) + 2 = 2 (read 3x3 box starting from pos 0 to 2) 

3 * (3/3) + 2 = 5 (read 3x3 box starting from pos 3 to 5) 
3 * (4/3) + 2 = 5 (read 3x3 box starting from pos 3 to 5) 
3 * (5/3) + 2 = 5 (read 3x3 box starting from pos 3 to 5) 

3 * (6/3) + 2 = 8 (read 3x3 box starting from pos 6 to 8) 
3 * (7/3) + 2 = 8 (read 3x3 box starting from pos 6 to 8) 
3 * (8/3) + 2 = 8 (read 3x3 box starting from pos 6 to 8) 

Answer 2

Просто говорят, IsValid() проверяет те условия, которые позволяют поставить другое значение в новое положение.

Например: он просматривает все строки выше/ниже; столбцы влево/вправо и проверяет, что предоставленное значение еще не существует.

Иными словами: перед «добавлением» нового номера необходимо выполнить различные условия, и этот метод просто проверяет, что плата с этим новым значением по-прежнему является законной.

Answer 3

Предполагалось, что комментарии будут полезны для объяснения кода.

/** your row and column index are based on 0, 
* and you evaluate the start index or lower bound for the 3x3 grid */ 
int x1 = 3 * (cell.row/3); 
int y1 = 3 * (cell.col/3); 
/** with the upper bound or the end index for the 3x3 grid 
* at postion = initial + 2 */ 
int x2 = x1 + 2; 
int y2 = y1 + 2; 

/** Iterate through the 3x3 to validate the same element is not present 
* twice in the 3x3 inner grid */ 
for (int x = x1; x <= x2; x++) 
    for (int y = y1; y <= y2; y++) 
     if (grid[x][y] == value) 
      return false; // false if its already there 

return true; 

Для нижнего и верхняя граница vaules, подумайте о группировки индексов 0-2, 3-5, 6-8 как в строках, так и в столбцах.