Кто-нибудь знает простой алгоритм проверки правильности конфигурации Sudoku? Самый простой алгоритм, который я придумал - это (для доски размером n) в псевдокоде
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
Но я совершенно уверен, что должно быть лучшее (в смысле более элегантного) решение. Эффективность совершенно не важна.
Вам нужно проверить все ограничения Sudoku:
что 6 проверок вообще.. с использованием подхода грубой силы. Некоторая математическая оптимизация может быть использована, если вы знаете размер платы (т.е. 3x3 или 9x9)
Изменить: объяснение ограничения суммы: проверка суммы сначала (и остановка, если сумма не равна 45) выполняется намного быстрее (и проще), чем проверка дубликатов. Она обеспечивает простой способ отбросить неправильное решение.
У Питера Норвига есть отличная статья о решении головоломок судоку (с питоном),
Может быть, это слишком много для того, что вы хотите сделать, но это отлично читается в любом случае
Просто подумайте: вам не нужно также проверять номера на каждом квадрате 3x3?
Я пытаюсь выяснить, возможно ли удовлетворять условиям строк и столбцов без правильной судоку
Проверьте каждую строку, столбец и поле так, чтобы они содержали числа 1-9 каждый, без дубликатов. Большинство ответов здесь уже обсуждают это.
Но как это сделать эффективно? Ответ: Используйте цикл, например
result=0;
for each entry:
result |= 1<<(value-1)
return (result==511);
Каждый номер устанавливает один бит результата. Если все 9 чисел уникальны, самые низкие 9 биты будут установлены. Таким образом, тест "проверка на дубликаты" - это всего лишь проверка того, что установлены все 9 бит, что совпадает с результатом тестирования == 511. Вам нужно сделать 27 таких проверок.. по одному для каждой строки, столбца и поля.
Создайте массив булевых строк для каждой строки, столбца и квадрата. Индекс массива представляет значение, которое было помещено в эту строку, столбец или квадрат. Другими словами, если вы добавите 5 во вторую строку, первый столбец, вы установите для строк [2] [5] значение true, а также столбцы [1] [5] и квадраты [4] [5], чтобы указать что строка, столбец и квадрат теперь имеют значение 5.
Независимо от того, как представляется ваша оригинальная доска, это может быть простой и очень быстрый способ проверить его на полноту и правильность. Просто возьмите числа в том порядке, в котором они появляются на доске, и начните строить эту структуру данных. Когда вы размещаете числа на доске, он становится операцией O (1), чтобы определить, дублируются ли какие-либо значения в данной строке, столбце или квадрате. (Вы также захотите проверить, что каждое значение является законным номером: если они дают вам пустое или слишком высокое количество, вы знаете, что плата не завершена.) Когда вы дойдете до конца доски, вы "Я знаю, что все значения верны, и больше не требуется проверка.
Кто-то также указал, что вы можете использовать любую форму Set для этого. Массивы, устроенные таким образом, являются всего лишь легкой и эффективной формой набора, который хорошо работает для небольшого последовательного фиксированного набора чисел. Если вы знаете размер своей доски, вы также можете сделать бит-маскировку, но это, вероятно, немного излишне утомительно, учитывая, что эффективность не является для вас большой сделкой.
Это мое решение в Python, я рад видеть его самым коротким:)
Код:
def check(sud):
zippedsud = zip(*sud)
boxedsud=[]
for li,line in enumerate(sud):
for box in range(3):
if not li % 3: boxedsud.append([]) # build a new box every 3 lines
boxedsud[box + li/3*3].extend(line[box*3:box*3+3])
for li in range(9):
if [x for x in [set(sud[li]), set(zippedsud[li]), set(boxedsud[li])] if x != set(range(1,10))]:
return False
return True
И выполнение:
sudoku=[
[7, 5, 1, 8, 4, 3, 9, 2, 6],
[8, 9, 3, 6, 2, 5, 1, 7, 4],
[6, 4, 2, 1, 7, 9, 5, 8, 3],
[4, 2, 5, 3, 1, 6, 7, 9, 8],
[1, 7, 6, 9, 8, 2, 3, 4, 5],
[9, 3, 8, 7, 5, 4, 6, 1, 2],
[3, 6, 4, 2, 9, 7, 8, 5, 1],
[2, 8, 9, 5, 3, 1, 4, 6, 7],
[5, 1, 7, 4, 6, 8, 2, 3, 9]]
print check(sudoku)
Создание наборов ячеек, где каждый набор содержит 9 ячеек и создает наборы для вертикальных столбцов, горизонтальных строк и квадратов 3x3.
Затем для каждой ячейки просто идентифицируйте множества, которые она часть, и проанализируйте их.
Вы можете извлечь все значения из набора (строка, столбец, поле) в список, отсортировать его, затем сравнить с "(1, 2, 3, 4, 5, 6, 7, 8, 9)
Я сделал это один раз для проекта класса. Я использовал в общей сложности 27 наборов для представления каждой строки, столбца и поля. Я бы проверял числа, когда добавлял их к каждому набору (каждое размещение номера заставляет номер добавлять 3 набора, строку, столбец и поле), чтобы убедиться, что пользователь вводил только цифры 1- 9. Единственный способ заполнить набор, если он был правильно заполнен уникальными цифрами. Если все 27 наборов заполнены, головоломка была решена. Настройка сопоставлений из пользовательского интерфейса на 27 наборов была немного утомительной, но остальная логика была реализована.
если сумма и, умножение строки /col равно правому числу 45/362880
Было бы очень интересно проверить:
when the sum of each row/column/box equals n*(n+1)/2
and the product equals n!
with n = number of rows or columns
этого достаточно правил судоку. Потому что это позволит использовать алгоритм O (n ^ 2), суммируя и умножая правильные ячейки.
Глядя на n = 9, суммы должны быть 45, продукты 362880.
Вы бы сделали что-то вроде:
for i = 0 to n-1 do
boxsum[i] := 0;
colsum[i] := 0;
rowsum[i] := 0;
boxprod[i] := 1;
colprod[i] := 1;
rowprod[i] := 1;
end;
for i = 0 to n-1 do
for j = 0 to n-1 do
box := (i div n^1/2) + (j div n^1/2)*n^1/2;
boxsum[box] := boxsum[box] + cell[i,j];
boxprod[box] := boxprod[box] * cell[i,j];
colsum[i] := colsum[i] + cell[i,j];
colprod[i] := colprod[i] * cell[i,j];
rowsum[j] := colsum[j] + cell[i,j];
rowprod[j] := colprod[j] * cell[i,j];
end;
end;
for i = 0 to n-1 do
if boxsum[i] <> 45
or colsum[i] <> 45
or rowsum[i] <> 45
or boxprod[i] <> 362880
or colprod[i] <> 362880
or rowprod[i] <> 362880
return false;
Некоторое время назад я написал контролер sudoku, который проверяет дубликат номера на каждой строке, дублирует номер на каждом столбце и дублирует номер на каждом поле. Мне бы очень понравилось, если бы кто-то мог придумать что-то вроде нескольких строк кода Linq.
char VerifySudoku(char grid[81])
{
for (char r = 0; r < 9; ++r)
{
unsigned int bigFlags = 0;
for (char c = 0; c < 9; ++c)
{
unsigned short buffer = r/3*3+c/3;
// check horizontally
bitFlags |= 1 << (27-grid[(r<<3)+r+c])
// check vertically
| 1 << (18-grid[(c<<3)+c+r])
// check subgrids
| 1 << (9-grid[(buffer<<3)+buffer+r%3*3+c%3]);
}
if (bitFlags != 0x7ffffff)
return 0; // invalid
}
return 1; // valid
}
Во-первых, вам нужно сделать логическое, "правильное". Затем сделайте цикл for, как указано выше. Код для цикла и всего после него (в java), как указано, где поле является двумерным массивом с равными сторонами, col - другой с теми же размерами, а l - 1D:
for(int i=0; i<field.length(); i++){
for(int j=0; j<field[i].length; j++){
if(field[i][j]>9||field[i][j]<1){
checking=false;
break;
}
else{
col[field[i].length()-j][i]=field[i][j];
}
}
}
Я не знаю точного алгоритма проверки полей 3x3, но вы должны проверить все строки в поле и col с помощью "/*array name goes here*/[i].contains(1)&&/*array name goes here*/[i].contains(2)" (продолжается до тех пор, пока вы не достигнете длины строки) внутри другого цикла.
Здесь хороший читаемый подход в Python:
from itertools import chain
def valid(puzzle):
def get_block(x,y):
return chain(*[puzzle[i][3*x:3*x+3] for i in range(3*y, 3*y+3)])
rows = [set(row) for row in puzzle]
columns = [set(column) for column in zip(*puzzle)]
blocks = [set(get_block(x,y)) for x in range(0,3) for y in range(0,3)]
return all(map(lambda s: s == set([1,2,3,4,5,6,7,8,9]), rows + columns + blocks))
Каждый квадрат 3x3 называется блоком, и из них 9 в сетке 3x3. Предполагается, что головоломка вводится как список списка, причем каждый внутренний список является строкой.
Скажем, int sudoku [0..8,0..8] является полем судоку.
bool CheckSudoku(int[,] sudoku)
{
int flag = 0;
// Check rows
for(int row = 0; row < 9; row++)
{
flag = 0;
for (int col = 0; col < 9; col++)
{
// edited : check range step (see comments)
if ((sudoku[row, col] < 1)||(sudoku[row, col] > 9))
{
return false;
}
// if n-th bit is set.. but you can use a bool array for readability
if ((flag & (1 << sudoku[row, col])) != 0)
{
return false;
}
// set the n-th bit
flag |= (1 << sudoku[row, col]);
}
}
// Check columns
for(int col= 0; col < 9; col++)
{
flag = 0;
for (int row = 0; row < 9; row++)
{
if ((flag & (1 << sudoku[row, col])) != 0)
{
return false;
}
flag |= (1 << sudoku[row, col]);
}
}
// Check 3x3 boxes
for(int box= 0; box < 9; box++)
{
flag = 0;
for (int ofs = 0; ofs < 9; ofs++)
{
int col = (box % 3) * 3;
int row = ((int)(box / 3)) * 3;
if ((flag & (1 << sudoku[row, col])) != 0)
{
return false;
}
flag |= (1 << sudoku[row, col]);
}
}
return true;
}
Предположим, что ваша доска идет от 1 - n.
Мы создадим контрольный массив, залейте его и проверим.
grid [0-(n-1)][0-(n-1)]; //this is the input grid
//each verification takes n^2 bits, so three verifications gives us 3n^2
boolean VArray (3*n*n) //make sure this is initialized to false
for i = 0 to n
for j = 0 to n
/*
each coordinate consists of three parts
row/col/box start pos, index offset, val offset
*/
//to validate rows
VArray( (0) + (j*n) + (grid[i][j]-1) ) = 1
//to validate cols
VArray( (n*n) + (i*n) + (grid[i][j]-1) ) = 1
//to validate boxes
VArray( (2*n*n) + (3*(floor (i/3)*n)+ floor(j/3)*n) + (grid[i][j]-1) ) = 1
next
next
if every array value is true then the solution is correct.
Я думаю, что это сделает трюк, хотя я уверен, что сделал пару глупых ошибок там. Возможно, я даже полностью пропустил лодку.
array = [1,2,3,4,5,6,7,8,9]
sudoku = int [][]
puzzle = 9 #9x9
columns = map []
units = map [] # box
unit_l = 3 # box width/height
check_puzzle()
def strike_numbers(line, line_num, columns, units, unit_l):
count = 0
for n in line:
# check which unit we're in
unit = ceil(n / unit_l) + ceil(line_num / unit_l) # this line is wrong - rushed
if units[unit].contains(n): #is n in unit already?
return columns, units, 1
units[unit].add(n)
if columns[count].contains(n): #is n in column already?
return columns, units, 1
columns[count].add(n)
line.remove(n) #remove num from temp row
return columns, units, line.length # was a number not eliminated?
def check_puzzle(columns, sudoku, puzzle, array, units):
for (i=0;i< puzzle;i++):
columns, units, left_over = strike_numbers(sudoku[i], i, columns, units) # iterate through rows
if (left_over > 0): return false
Без тщательной проверки, с верхней части головы, это должно работать (с небольшой отладкой), а только дважды зацикливаться. O (n ^ 2) вместо O (3 (n ^ 2))
Вот статья математического профессора J.F. Crook: Канонирно-бумажный алгоритм для решения головоломок Судоку
Этот документ был опубликован в апреле 2009 года, и он получил много рекламы в качестве определенного решения Sudoku (проверьте google для "J.F.Crook Sudoku" ).
Помимо алгоритма, есть также математическое доказательство того, что алгоритм работает (профессор признался, что он не считает Судоку очень интересным, поэтому он бросил некоторую математику в бумаге, чтобы сделать ее более увлекательной).
Я бы написал интерфейс, который имеет функции, которые получают поле sudoku и возвращает true/false, если это решение. Затем реализуйте ограничения как одиночные классы проверки на ограничение.
Чтобы проверить только повторение всех классов ограничений и когда все проходят судоку, это правильно. Для ускорения поставьте те, которые, скорее всего, не сработают спереди и остановят в первом результате, который указывает на недопустимое поле.
Довольно общий шаблон.; -)
Вы можете, конечно, улучшить это, чтобы дать подсказки, какое поле, по-видимому, неправильно и т.д.
Первое ограничение, просто проверьте, заполнены ли все поля. (Простой цикл) Вторая проверка, если все числа находятся в каждом блоке (вложенные циклы) Третья проверка для полных строк и столбцов (почти такая же процедура, как и выше, но с другой схемой доступа)
Вот мой в C. Пройдите только каждый квадрат один раз.
int checkSudoku(int board[]) {
int i;
int check[13] = { 0 };
for (i = 0; i < 81; i++) {
if (i % 9 == 0) {
check[9] = 0;
if (i % 27 == 0) {
check[10] = 0;
check[11] = 0;
check[12] = 0;
}
}
if (check[i % 9] & (1 << board[i])) {
return 0;
}
check[i % 9] |= (1 << board[i]);
if (check[9] & (1 << board[i])) {
return 0;
}
check[9] |= (1 << board[i]);
if (i % 9 < 3) {
if (check[10] & (1 << board[i])) {
return 0;
}
check[10] |= (1 << board[i]);
} else if (i % 9 < 6) {
if (check[11] & (1 << board[i])) {
return 0;
}
check[11] |= (1 << board[i]);
} else {
if (check[12] & (1 << board[i])) {
return 0;
}
check[12] |= (1 << board[i]);
}
}
}
Вот что я сделал для этого:
boolean checkers=true;
String checking="";
if(a.length/3==1){}
else{
for(int l=1; l<a.length/3; l++){
for(int n=0;n<3*l;n++){
for(int lm=1; lm<a[n].length/3; lm++){
for(int m=0;m<3*l;m++){
System.out.print(" "+a[n][m]);
if(a[n][m]<=0){
System.out.print(" (Values must be positive!) ");
}
if(n==0){
if(m!=0){
checking+=", "+a[n][m];
}
else{
checking+=a[n][m];
}
}
else{
checking+=", "+a[n][m];
}
}
}
System.out.print(" "+checking);
System.out.println();
}
}
for (int i=1;i<=a.length*a[1].length;i++){
if(checking.contains(Integer.toString(i))){
}
else{
checkers=false;
}
}
}
checkers=checkCol(a);
if(checking.contains("-")&&!checking.contains("--")){
checkers=false;
}
System.out.println();
if(checkers==true){
System.out.println("This is correct! YAY!");
}
else{
System.out.println("Sorry, it not right. :-(");
}
}
private static boolean checkCol(int[][]a){
boolean checkers=true;
int[][]col=new int[][]{{0,0,0},{0,0,0},{0,0,0}};
for(int i=0; i<a.length; i++){
for(int j=0; j<a[i].length; j++){
if(a[i][j]>9||a[i][j]<1){
checkers=false;
break;
}
else{
col[a[i].length-j][i]=a[i][j];
}
}
}
String alia="";
for(int i=0; i<col.length; i++){
for(int j=1; j<=col[i].length; j++){
alia=a[i].toString();
if(alia.contains(""+j)){
alia=col[i].toString();
if(alia.contains(""+j)){}
else{
checkers=false;
}
}
else{
checkers=false;
}
}
}
return checkers;
}
Вы можете проверить, разрешено ли судоку, двумя способами:
Наивным решением будет итерация по каждому квадрату и проверка того, является ли число уникальным в строке, номер столбца, который занимает номер.
Но есть лучший способ.
Это требует только проверки каждой строки, столбца и блока вместо того, чтобы делать это для каждого числа. Простой реализацией было бы иметь битовое поле чисел 1 через 9 и удалять их, когда вы повторяете столбцы, строки и блоки. Если вы попытаетесь удалить недостающее число или если поле не пустое, когда вы закончите, то sudoku не будет правильно решена.
def solution(board):
for i in board:
if sum(i) != 45:
return "Incorrect"
for i in range(9):
temp2 = []
for x in range(9):
temp2.append(board[i][x])
if sum(temp2) != 45:
return "Incorrect"
return "Correct"
board = []
for i in range(9):
inp = raw_input()
temp = [int(i) for i in inp]
board.append(temp)
print solution(board)
Здесь очень сжатая версия в Swift, которая использует только массив Ints для отслеживания групп из 9 чисел и только итерации по судоку один раз.
import UIKit
func check(_ sudoku:[[Int]]) -> Bool {
var groups = Array(repeating: 0, count: 27)
for x in 0...8 {
for y in 0...8 {
groups[x] += 1 << sudoku[x][y] // Column (group 0 - 8)
groups[y + 9] += 1 << sudoku[x][y] // Row (group 9 - 17)
groups[(x + y * 9) / 9 + 18] += 1 << sudoku[x][y] // Box (group 18 - 27)
}
}
return groups.filter{ $0 != 1022 }.count == 0
}
let sudoku = [
[7, 5, 1, 8, 4, 3, 9, 2, 6],
[8, 9, 3, 6, 2, 5, 1, 7, 4],
[6, 4, 2, 1, 7, 9, 5, 8, 3],
[4, 2, 5, 3, 1, 6, 7, 9, 8],
[1, 7, 6, 9, 8, 2, 3, 4, 5],
[9, 3, 8, 7, 5, 4, 6, 1, 2],
[3, 6, 4, 2, 9, 7, 8, 5, 1],
[2, 8, 9, 5, 3, 1, 4, 6, 7],
[5, 1, 7, 4, 6, 8, 2, 3, 9]
]
if check(sudoku) {
print("Pass")
} else {
print("Fail")
}
Одна небольшая оптимизация, которую вы можете сделать, заключается в том, что вы можете проверять наличие дубликатов в строке, столбце или поле за O (n) время, а не за O (n ^ 2): когда вы перебираете набор чисел, вы добавляете каждое к хэшсет. В зависимости от языка, вы можете использовать настоящий хэш-набор, который представляет собой поиск и вставку с постоянным временем; тогда проверка на дубликаты может быть выполнена на том же шаге, проверяя, была ли вставка успешной или нет. Это небольшое улучшение в коде, но переход от O (n ^ 2) к O (n) является существенной оптимизацией.
Если вам нужен решатель, здесь можно найти "крутой" алгоритм (в 3 строках):
http://www.ecclestoad.co.uk/blog/2005/06/02/sudoku_solver_in_three_lines_explained.html