По решению судоку

Question

Может кто-нибудь помочь мне понять это решение :

 Initialize 2D array with 81 empty grids (nx = 9, ny = 9)
 Fill in some empty grid with the known values
 Make an original copy of the array
 Start from top left grid (nx = 0, ny = 0), check if grid is empty
 if (grid is empty) {
   assign the empty grid with values (i)
   if (no numbers exists in same rows & same columns same as (i) & 3x3 zone (i) is currently in)
     fill in the number
   if (numbers exists in same rows & same columns same as (i) & 3x3 zone (i) is currently in)
     discard (i) and repick other values (i++)
 }
 else {
   while (nx < 9) {
     Proceed to next row grid(nx++, ny)
     if (nx equals 9) {
       reset nx = 1
       proceed to next column grid(nx,ny++)
       if (ny equals 9) {
         print solution
       }
     }
   }
 }

Answer 1

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

Функция с именем safe определяет, допустимо ли в настоящее время помещать значение n в определенную ячейку, проверяя, какие значения уже помещены в строку, столбец и поле.

Это один из самых простых (и самых медленных) способов решить судоку.

Answer 2

Есть много способов решить судоку (не знаю, если вы заинтересованы в нем в целом). По сути, это проблема удовлетворения ограничений, и вы можете применять свои любимые методы проверки согласованности (например, AC3) для распространения ограничений и сокращения явно бесплодных путей гораздо раньше. Каждая из ваших переменных - это квадрат, домен, который может принимать каждая переменная, это целые числа от 1 до 9. Ограничения - это AllDiff для различных подмножеств ячеек.

Вы также можете сформулировать ее как задачу целочисленного линейного программирования и просто разрешить ее вашему любимому движку ILP (например, lp_solve)!

Answer 3

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

Чтобы заполнить сетку по окончании алгоритма, можно заставить функцию решения возвращать значение true / false и затем решать, следует ли выполнять обратную трассировку на основе результата внутренних вызовов.