Sudoku 1. díl
V prvním díle tohoto mini seriálu o sudoku se budeme zabývat jak programově ověřit zdali zadaná data v poli jsou sudoku popřípadě zadání sudoku (neobsahuje kontrolu zdali zadaná data se dále nechají řešit jako sudoku). Dále popsaný algoritmus jsem vymyslel z hlavy a nemusí být zrovna nejoptimálnější ale je plně funkční a poměrně rychlí.
Pro začátek zde uvedu celý algoritmus s popiskami a poté jej níže podrobně popíšu.
Sudoku musí být uložené v poli HP, toto pole je dvourozměrné: Dim HP(8,8) as integer
Private Function kontrola() As Boolean
Dim pole1(9) As Integer 'Pole kde se budou ukládat informace o projdutém řádku
Dim pole2(9) As Integer 'Pole kde se budou ukládat informace o projdutém slopci
Dim pole3(3, 9) As Integer 'Pole kde se budou ukládat informace o projdutém čtverci
Dim I As Integer, J As Integer, UB As Integer, Conp As Integer, chyba As Integer, UR As Integer
chyba = 0
For I = 0 To 8 'I je číslo sloupce
Conp = Conp + 1 'číslo které se uloží do pole pro kontrolu
If I Mod 3 = 0 Then UR = UR + 1 'Zvětšení UR při každém třetím řádku
For J = 0 To 8 'J je číslo řádku
If (pole1(HP(I, J)) = Conp And HP(I, J) > 0) Or (pole2(HP(J, I)) = Conp And HP(J, I) > 0) Then 'viz popis níže
chyba = 1 'Pokud je zjištěn konflikt (v jednom řádku nebo sloupci jsou stejná čísla)
SCH = 1
End If
pole1(HP(I, J)) = Conp 'Ulžení hodnoty Conp do pole1
pole2(HP(J, I)) = Conp 'Ulžení hodnoty Conp do pole1
If J Mod 3 = 0 Then UB = UB + 1 End If 'při každém třetím řádku se zvedne UB o jednu
If pole3(UB, HP(I, J)) = UR And HP(I, J) > 0 Then
chyba = 1 'Pokud je zjištěn konflikt (v jednom řádku nebo sloupci jsou stejná čísla)
SCH = 1
End If
pole3(UB, HP(I, J)) = UR 'Ulžení hodnoty UR do pole1
Next J
UB = UB - 3 'Po ukončení každé řádky odečteme od UR 3 (vrátíme se k brvnímu čtverci)
Next I
If chyba <> 1 Then kont = True Else kont = False
End Function
Než začnu celý cyklus popisovat tak vysvětlím jak funguje. Budu vysvětlovat jen situaci jednoho řádku, ale obdobný princip je použit u procházení sloupců a čtverců.
Na každé řádce by se mělo vyskytovat každé číslo pouze jednou. Procházíme pole a vždy do předem připraveného pole zapíšeme pro každý řádek jedinečnou hodnotu, Kde hodnota napsaná v daném poli sudoku se použije jako index našeho pole. Pokud tedy bude v sudoku číslo dva na námi kontrolovaném řádku- pole1(2)=Conp, pokud tedy se některé číslo vyskytne v řádku dvakrát tak již při druhém výskytu bude v poli (pole1(2)) uložena hodnota Conp. Je jasné že napřed muíme provádět test jestli není v buňce již uložena daná hodnota a pak teprve ji tam zapsat.
Celí algoritmus je uzavřen do dvou cyklů (cyklus s proměnnou I a cyklus s proměnnou J). Na začátku cyklu I zvedneme hodnotu proměnné Conp, u této proměnné je jedno jakou bude nabývat hodnotu ale musí být větší než nula a nesmí se opakovat (při každém započatém cyklu se musí její hodnota změnit).Poté si nastavýme hodnotu proměnné UR (pokud daný řádek je první řádek čtverce); Obdobná funkce jako Conp. V proměnné UR je uložeo číslo které je jedinečné pro danou trojci čtverců. Následuje cyklus J který nám již prochází daný řádek který je určen hodnotou proměnný I.
Dále následuje podmínka na ověření zdali se již aktuální číslo nevyskytuje ve sloupci nebo řádku (určeno hodnotou I a J).Pokud ano uloží se do proměnné chyba a SH jednička. Za podmínkou následuje samotné zapsání hodnot do pole napřed pro řádek a poté pro sloupec. Dále následuje výpočet hodnoty UB která udává do kterého čtverce dané číslo patří. Další podmínka ověřuje, jestli se ve čtverci toto číslo již nevyskytlo a pod ní je přiřazení hodnoty do pole3. Po skončení cyklu J se od UB odečte 3, to z toho důvodu aby jsme při dalším průchodu pole začínali opět od prvního (v programu od nultého) čtverce.
S výše napsaného vyplívá že tento algoritmus vykoná 81 kroků ve kterých ověří zdali se v řádce, sloupci nebo čtverci nevyskytuje nějaké číslo dvakrát.
Příště si ukážeme jak řešit jednodušší sudoku pomocí VB
|
