Решение Sudoku на Java, используя обратную трассировку и рекурсию

Ответ 1

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

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

Следовательно, данные числа будут представлены в виде одноэлементных множеств, а пустые, которые вы можете инициализировать с помощью {1,2,3,4,5,6,7,8,9}. И тогда цель состоит в том, чтобы уменьшить неединичные клетки до тех пор, пока все клетки не станут одиночными.

(Обратите внимание, что при решении судоку с карандашом и бумагой часто записывают небольшие числа в пустые ячейки, чтобы отслеживать, какие числа там возможны, насколько это удалось решить.)

И затем, когда "пробует следующий номер", вы берете следующий номер из набора. У указанных ячеек нет следующего номера, поэтому вы не можете их изменить. Таким образом, трудности, которые вы описываете, исчезают (хотя бы немного).

------ ИЗМЕНИТЬ, ПОСЛЕ УЧИТЫВАЯ, ЧТО НЕОБХОДИМО БОРТОВОЙ СИЛ.

Ваш учитель явно хочет научить вас чудесам рекурсии. Очень хорошо!

В этом случае нам просто нужно знать, какие ячейки указаны, а какие нет.

Особый простой способ, который можно использовать здесь, состоит в том, чтобы поместить 0 в любую не заданную ячейку, поскольку заданные ячейки по определению являются одним из 1,2,3,4,5,6,7,8,9.

Теперь подумайте о том, как заставить рекурсивную грубую силу работать.

У нас есть цель решить sudoku с n пустых ячеек. Если бы у нас была функция, которая бы разрешала судоку с n-1 пустыми ячейками (или сигнализировала, что она не разрешима), тогда эта задача будет легкой:

let c be some empty cell.
let f be the function that solves a sudoku with one empty cell less.
for i in 1..9
   check if i can be placed in c without conflict
   if not continue with next i
   place i in c
   if f() == SOLVED then return SOLVED
return NOTSOLVABLE

Этот псевдокод выбирает какую-то пустую ячейку, а затем пробует все числа, которые там подходят. Поскольку судоку имеет - по определению - только одно решение, есть только следующие случаи:

• мы выбрали правильный номер. Тогда f() найдет остальную часть решения и вернет SOLVED.
• мы выбрали неверный номер: f() будет сигнализировать, что судоку не разрешимо с этим неправильным номером в нашей ячейке.
• мы проверили все числа, но никто не был прав: тогда у нас есть неразрешимая судоку, и мы сигнализируем об этом нашему вызывающему.

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

Если мы сейчас подумаем о том, как выглядит наша таинственная, но неизвестная функция f(), получается, что она будет почти такой же, как у нас уже есть! Единственный случай, который мы еще не рассмотрели, это судоку с 0 пустыми ячейками. Это означает, что если мы обнаружим, что больше нет пустых ячеек, мы знаем, что мы только что решили судоку и вернемся только РЕШИТЬ.

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

В нашем случае мы знаем, что судоку разрешимо, более того, мы знаем, что оно имеет ровно одно решение. Поместив кусок в пустую ячейку, мы приближаемся к решению (или к диагнозу, что его нет), и рекурсивно возвращаем новую, меньшую проблему к функции, которую мы просто пишем. Основным случаем является "Судоку с 0 пустыми ячейками", который на самом деле является решением.

(Все становится немного сложнее, если есть много возможных решений, но мы оставляем это для следующего урока.)

Ответ 2

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

Рассмотрим 3 9x9 булевых двумерных массивов:

boolean row[9][9], col[9][9], minigrid[9][9]

Мы будем использовать первый массив для проверки наличия числа в одной строке, второго массива для проверки наличия числа в одном столбце, а третий для мини-сетки.

Предположим, вы хотите поместить число n в ячейку i, j. Вы проверите, истинна ли строка [i] [n-1]. Если да, то строка i ^th уже содержит n. Аналогично, вы проверите, истинно ли col [j] [n-1] и minigrid [gridnum] [n-1].

Здесь gridnum - это индекс мини-сетки, в котором находится ячейка, в которую вы хотите вставить число. Чтобы вычислить номер мини-сетки для ячейки i, j разделите я и j на 3, умножьте интегральную часть первого на 3 и добавьте его в неотъемлемую часть последнего.

Это выглядит так:

gridnum = (i/3)*3 + j/3

Изучая значения i/3 и j/3 для всех я и j, вы получите представление о том, как это работает. Кроме того, если вы поместите число в ячейку, обновите также массивы. Например. строка [i] [n-1] = true

Если есть часть, которую вы не понимаете, опубликуйте комментарий, и я отредактирую свой ответ, чтобы объяснить это.

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

boolean F( i, j) // invoke this function with i = j = 0
{
If i > 8: return true // solved

for n in 1..9
 {
 check if n exists in row, column, or mini grid by the method I described

 if it does: pass ( skip this iteration )

 if it doesn't
  {
   grid[i][j] = n
   update row[][], col[][], minigrid[][]

   if F( if j is 8 then i+1 else i, if j is 8 then 0 else j+1 ) return true // solved
  }
 }
 return false // no number could be entered in cell i,j
}

Ответ 3

Я предлагаю передать и текущую строку и столбец рекурсивному методу затем найдите все допустимые числа для ячейки THAT, для каждого разрешенного числа рекурсивно вызовите метод для следующего столбца (или следующей строки, если в последнем столбце), и отмените перемещение, если оно приведет к мертвой дорожке

public boolean fillCell(int r, int c) {
    if last row and last cell {
        //report success
        return true
    }
    for i 1 to 9 {
        if can place i on r, c {
            board[r][c] = i
            if !fillCell(next empty row, next empty column) { //DONT change r or c here or you will not be able to undo the move
                board[r][c] = 0
            }
            /*
            else {
                return true; //returning true here will make it stop after 1 solution is found, doing nothing will keep looking for other solutions also
            }
            */

        }
    }
    return false        
}

Ответ 4

Я бы проверял каждую ячейку и возвращал шаг рекурсии, если решение не найдено.

Более подробно: Перейдите к следующей ячейке, если значение x == 0, проверьте, будет ли x + 1 верным, если true, перейдите в следующую ячейку, вызвав метод рекурсивно со следующей возможной ячейкой. Если число недопустимо, проверьте x + 2 и т.д., Если число недействительно, верните false и повторите шаг x + 1 в предыдущем вызове. Если вы нажмете ячейку с номером внутри, не вызывайте рекурсию, а переходите к следующему, поэтому вам не нужно указывать какие-либо предварительно введенные ячейки.

Псевдокод:

fillcell cell
 while cell is not 0
  cell = next cell
 while cell value < 10
  increase cell value by one
  if cell is valid 
    if fillcell next cell is true
      return true
return false

Не уверен, что это правильно, но должно показать эту идею.

Ответ 5

некоторые идеи, которые могут быть полезны (относительно рекурсии и возврата)

//some attributes you might need for storing e.g. the configuration to track back to.

boolean legal(Configuration configuration) {

}

int partSolution(Configuration configuration) {
  if (legal(configuration))
    return partSolution(nextConfiguration())
  else
    return partSolution(previousConfiguration())    
}

Configuration nextConfiguration() {
 //based on the current configuration and the previous tried ones,
 //return the next possible configuration:
 //next number to enter, next cell to visit
}

Configuration previousConfiguration() {
 //backtrack
}

solve () {
  call partSolution with start configuration while partSolution < 9x9
}

напишите класс конфигурации, который содержит сетку с введенными числами и некоторыми другими атрибутами, такими как размер и число вводимых чисел, и подумайте о том, что еще нужно