Алгоритм Голанга Судоку не работает

Question

Я очень новичок в Голанге, я пытаюсь сделать судоку с алгоритмом возврата. Но когда я запускаю свою программу, ошибок нет, а отображается только неполная сетка, с пустыми регистрами вот мой код:

package main

import "fmt"

var sudoku = [9][9]int{
    {9, 0, 0, 1, 0, 0, 0, 0, 5},
    {0, 0, 5, 0, 9, 0, 2, 0, 1},
    {8, 0, 0, 0, 4, 0, 0, 0, 0},
    {0, 0, 0, 0, 8, 0, 0, 0, 0},
    {0, 0, 0, 7, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 2, 6, 0, 0, 9},
    {2, 0, 0, 3, 0, 0, 0, 0, 6},
    {0, 0, 0, 2, 0, 0, 9, 0, 0},
    {0, 0, 1, 9, 0, 4, 5, 7, 0},
  }

func main(){
  IsValid(sudoku, 0)
  Display(sudoku)
}

func Display(sudoku[9][9] int){
  var x, y int

  for x = 0; x < 9; x++ {
        fmt.Println("")
        if(x == 3 || x == 6){
          fmt.Println(" ")
        }
      for y = 0; y < 9; y++ {
        if(y == 3 || y == 6){
          fmt.Print("|")
        }
         fmt.Print(sudoku[x][y])
      }

   }

}

func AbsentOnLine(k int, sudoku [9][9]int, x int) bool {
  var y int
    for y=0; y < 9; y++ {
        if (sudoku[x][y] == k){
            return false
          }
        }
    return true
}

func AbsentOnRow(k int, sudoku [9][9]int, y int) bool {
  var x int
  for x=0; x < 9; x++{
       if (sudoku[x][y] == k){
           return false;
         }
       }
   return true;
}

func AbsentOnBloc(k int, sudoku [9][9]int, x int, y int) bool {
  var firstX, firstY int;
  firstX =  x-(x%3)
  firstY =  y-(y%3)
  for x = firstX; x < firstX+3; x++ {
        for y = firstY; y < firstY+3; y++ {
            if (sudoku[x][y] == k){
                return false;
              }
        }
      }
    return true;

}

func IsValid(sudoku [9][9]int, position int) bool {

  if (position == 9*9){
        return true;
      }

      var x, y, k int

    x = position/9
    y = position%9

    if (sudoku[x][y] != 0){
        return IsValid(sudoku, position+1);
      }

    for k=1; k <= 9; k++ {
        if (AbsentOnLine(k,sudoku,x) && AbsentOnRow(k,sudoku,y) && AbsentOnBloc(k,sudoku,x,y)){
            sudoku[x][y] = k;

            if (IsValid(sudoku, position+1)){
                return true;
              }
        }
    }
    sudoku[x][y] = 0;
    return false;

}

Я получаю это в консоли:

900|100|005
005|090|201
800|040|000

000|080|000
000|700|000
000|026|009

200|300|006
000|200|900
001|904|570

Я не понимаю, почему это не завершает сетку, есть у кого-нибудь идеи?

Answer 1

Ваш IsValid Функция изменяет содержимое судоку. Проблема, собственно, в вашем коде, как есть, меняет только копию судоку. Вам нужно передать его как указатель, если он должен изменить фактическую переменную.

Вот изменения, которые вам нужны в вашем коде, это всего пять символов:

func main() {
    IsValid(&sudoku, 0)
    Display(sudoku)
}

// ...

func IsValid(sudoku *[9][9]int, position int) bool {

// ...

if AbsentOnLine(k, *sudoku, x) && AbsentOnRow(k, *sudoku, y) && AbsentOnBloc(k, *sudoku, x, y) {

Answer 2

Я не знаю Голанга, но я написал алгоритм решения судоку с использованием возврата.

Ваш код повторяет доску только один раз. Вы начинаете с position=0Ваш код, чем итерируется по доске, если позиция имеет нулевое значение, вы пытаетесь значения 1-9, и если это не работает, вы переходите к следующей позиции. когда position=81, твой код останавливается.

Вы добавили новые значения в доску с вашим Isvalid функции, но вы больше не перебираете новую доску, чтобы посмотреть, помогут ли эти новые значения AbsentOn... функция для возврата нового значения, отличного от предыдущей итерации. Вы должны повторять свою доску снова и снова, пока не будете уверены, что нет 0 ценные клетки.

Это причина, по которой вам приходится много 0 на доске в конце вашей программы. Ваша программа повторяется только один раз, она не может решить ваш пример судоку с первой попытки. Он должен добавлять новые значения в доску и облегчать судоку с каждой итерацией.

---

Еще одна проблема - ваш код не дает обратной связи. Например, это дает 1 в пустую клетку. Сначала это кажется странным, но это не значит, что окончательное значение этой ячейки должно быть 1, Это может измениться, потому что в ваших следующих итерациях вы понимаете, что есть другая ячейка, которая может принимать только значение 1так что теперь вы должны вернуться к своей первоначальной ячейке и найти новое значение, отличное от 1, Ваш код также не может этого сделать. Вот почему люди ставят некоторые возможные значения рядом с клеткой, когда они не уверены.

---

Похоже, ваша проблема с алгоритмом. Вы должны понимать алгоритм возврата. Вы можете попробовать его на другом языке, который вы хорошо знаете, а затем перенести его на golang(я написал на C++). Кроме этого, ваш код golang легко читается, и я не вижу проблем, связанных с golang.