检查数独字段的一种很酷的算法? [英] 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屋!