Решатель судоку на Java с использованием обратного отслеживания и рекурсии
Я программирую решатель судоку на Java для сетки 9x9.
У меня есть методы для:
печати сетки
инициализации плата с заданными значениями
тестирование на конфликты (если тот же номер находится в той же строке или в подсетке 3x3)
метод размещения цифр по одной, который требует больше всего работы.
До того, как я подробно рассмотрите этот метод, имейте в виду, что я должен использовать рекурсию для его решения, а также обратное отслеживание (см. пример апплета здесь http://www.heimetli.ch/ffh/simplifiedsudoku.html )
Кроме того, я решаю эту судоку, двигаясь вертикально вниз, начиная сверху слева, через первый столбец, затем через второй столбец и т. Д.
На данный момент у меня есть следующее:
public boolean placeNumber(int column){
if (column == SUDOKU_SIZE){ // we have went through all the columns, game is over
return true;
}
else
{
int row=0; //takes you to the top of the row each time
while (row < SUDOKU_SIZE) loops through the column downwards, one by one
{
if (puzzle[row][column]==0){ //skips any entries already in there (the given values)
puzzle[row][column]=1; //starts with one
while(conflictsTest(row,column)){ //conflictsTest is the method I wrote, which checks if the given parameters are in conflict with another number
puzzle[row][column] += 1;
}
//BACK TRACKING
placeNumber(column); //recursive call
}
else{
row++; // row already has a number given, so skip it
}
}
column++; // move on to second column
placeNumber(column);
}
return false; // no solutions to this puzzle
}
Где я пометил BACKTRACKING, я считаю, что оставшаяся часть моего кода должна быть перемещена.
Я придумал что-то вроде:
- если значение равно 10, установите это значение обратно на ноль, вернитесь на строку назад и увеличьте это значение на 1
Эта «стратегия» обратного отслеживания «не работает» t точно работает по нескольким причинам:
что, если предыдущая строка была заданным значением (иначе говоря, я не должен увеличивать ее или касаться ее, а вместо этого возвращаюсь к последнему значению, которое я поместил туда)
что, если бы предыдущее значение было 9. и если бы я увеличил его на 1, теперь мы находимся на 10, что не сработает.
Кто-нибудь может мне помочь?
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 , разделите i & амп; j на 3, умножьте неотъемлемую часть первого на 3 и добавьте его к неотъемлемой части последнего.
Вот как это выглядит:
gridnum = (i/3)*3 + j/3
Посмотрев на значения i / 3 и j / 3 для всех i и j, вы получите представление о том, как это работает. Также, если вы поместите число в ячейку, обновите и массивы. Например. row [i] [n-1] = true
Если есть часть, которую вы не понимаете, оставьте комментарий, и я отредактирую свой ответ, чтобы объяснить его.
Во-вторых , с использованием рекурсии & amp; Отступить, чтобы решить это довольно легко.
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
}
Я бы проверил каждую ячейку и вернулся бы к шагу рекурсии, если решение не найдено.
Более подробно: перейти к следующей ячейке, если значение 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
Не уверен, что это правильно, но это должно показать идею.