在数独求解 [英] On Sudoku solving

问题描述

是否有人可以帮助我了解<一href="http://en.wikipedia.org/wiki/Algorithmics_of_Sudoku#Example_of_a_brute_force_Sudoku_solver_.28in_C.29"相对=nofollow>这个解决方案：

 初始化二维数组与81空网格（NX = 9，NY = 9）
 在一些空网格填充与已知值
 使该阵列的原始副本
 从左上角网格（NX = 0，NY = 0）开始，检查网格是空的
 如果（格为空）{
   分配与价值观的空网格（I）
   如果（没有数字存在于相同的行和安培;相同的列相同的是（i）及3×3区（i）是当前在）
     填写数量
   如果（号码存在于相同的行和安培;相同的列相同的是（i）及3×3区（i）是当前在）
     丢弃（i）和重新检料等值（我+ +）
 }
 其他 {
   而（NX＆LT; 9）{
     继续执行下一行网格（NX ++，NY）
     如果（NX等于9）{
       复位NX = 1
       继续下柱网（NX，NY ++）
       如果（纽约州等于9）{
         打印解决方案
       }
     }
   }
 }
 

解决方案

这是一个简单的蛮力解决者。它从左上方，工作左至右逐行，试图将每个可能数量到每个正方形，并​​继续通过使用递归调用。如果失败，它将回溯并尝试不同的选择。

调用的函数安全确定它是否是当前的法律把值 N 在某些细胞，通过检查其值已放置在该行，列和框

它是解决数独最简单的（最慢）的方式之一。

Can someone please help me understand this solution:

 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
       }
     }
   }
 }

解决方案

It's a simple brute force solver. It starts from the top left, working left to right line by line, trying to place each possible number into each square, and continuing by using a recursive call. On failure it backtracks and tries a different alternative.

The function called safe determines whether it is currently legal to place the value n in a certain cell, by checking which values have already been placed in the row, column and box.

It's one of the simplest (and slowest) ways to solve a Sudoku.

这篇关于在数独求解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！