检查数独字段的一种很酷的算法？ [英] A cool algorithm to check a Sudoku field?

问题描述

有人知道一种简单的算法来检查Sudoku配置是否有效吗？我想出的最简单的算法是（对于一块大小为n的电路板）用伪代码

Does anyone know a simple algorithm to check if a Sudoku-Configuration is valid? The simplest algorithm I came up with is (for a board of size n) in Pseudocode

for each row
  for each number k in 1..n
    if k is not in the row (using another for-loop)
      return not-a-solution

..do the same for each column

但是我很确定必须有更好的选择（从更优雅的意义上讲）解。效率并不重要。

But I'm quite sure there must be a better (in the sense of more elegant) solution. Efficiency is quite unimportant.

推荐答案

您需要检查Sudoku的所有约束条件：

You need to check for all the constraints of Sudoku :

• 检查每一行的总和


• 检查每一列的总和


• 检查总和在每个框上


• 在每一行上检查重复数字


• 在每一列上检查重复数字


• 在每个盒子上检查重复的数字

• check the sum on each row
• check the sum on each column
• check for sum on each box
• check for duplicate numbers on each row
• check for duplicate numbers on each column
• check for duplicate numbers on each box

总共使用了6个校验..使用蛮力方法。

that's 6 checks altogether.. using a brute force approach.

如果您知道棋盘的大小（例如3x3或9x9），可以使用某种数学优化方法

Some sort of mathematical optimization can be used if you know the size of the board (ie 3x3 or 9x9)

编辑：求和约束的解释：与检查重复项相比，首先检查和（如果和不为45，则停止检查）要快得多（并且更简单）。它提供了一种丢弃错误解决方案的简便方法。

Edit: explanation for the sum constraint: Checking for the sum first (and stoping if the sum is not 45) is much faster (and simpler) than checking for duplicates. It provides an easy way of discarding a wrong solution.

这篇关于检查数独字段的一种很酷的算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！