Eötvös Loránd Tudományegyetem. Informatikai Kar. Média- és Oktatásinformatika Tanszék. Sudoku megoldó. programozó matematikus szak

Eötvös Loránd Tudományegyetem Informatikai Kar Média- és Oktatásinformatika Tanszék

Sudoku megoldó

Témavezető: Tarcsi Ádám

Készítette: Kurucz Attila

egyetemi tanársegéd

nappali tagozat programozó matematikus szak

Budapest, 2011

Tartalomjegyzék I.

Egy-két szó a sudokuról ..................................................................................................3

II.

Felhasználói dokumentáció ............................................................................................4 Program célja .................................................................................................................................4 Hardver-szoftver követelmények ...................................................................................................4 Telepítés ........................................................................................................................................4 A program részei ............................................................................................................................4 A program használata ....................................................................................................................4 Ablak elemei ..................................................................................................................................5 Start ........................................................................................................................................................ 5 Clear ........................................................................................................................................................ 5 Reset ....................................................................................................................................................... 5 Exit .......................................................................................................................................................... 5 Heruistic type .......................................................................................................................................... 5 Add field .................................................................................................................................................. 5 Generate ................................................................................................................................................. 6 Speed ...................................................................................................................................................... 6 Find all solution ....................................................................................................................................... 6 Backtrack number.................................................................................................................................... 6 Információs sáv........................................................................................................................................ 6

Menü elemei ..................................................................................................................................6 File .......................................................................................................................................................... 6 Options.................................................................................................................................................... 6

Find all solutions megoldásainak megtekintése .............................................................................7

III. Fejlesztői dokumentáció .................................................................................................9 Rejtvény mentése fájlba ..............................................................................................................27 Backtrack algoritmus a sudoku táblán .........................................................................................30 Find all solutions ..........................................................................................................................31 Példa egy visszalépésre ................................................................................................................31 Tábla generálása ..........................................................................................................................32

IV.

Heurisztikák..............................................................................................................33

Sorfolytonos (From index) ...........................................................................................................33 Legjobb pozíció (Best position) ....................................................................................................33 Véletlen pozíció (Random index) .................................................................................................34

V.

Tesztelési terv és statisztikák .......................................................................................35 Tesztelési terv ..............................................................................................................................35 Rossz input ............................................................................................................................................ 35 Üres input.............................................................................................................................................. 35 Normál input ......................................................................................................................................... 35

Statisztikák...................................................................................................................................35 Tesztelés a következő gépen történt ...................................................................................................... 35 Eredmények .......................................................................................................................................... 36

VI.

Fejlesztési lehetőségek, forráskód és dokumentáció ................................................37

Fejlesztési lehetőségek ................................................................................................................37 Forráskód és dokumentáció .........................................................................................................37

VII.

Összefoglalás............................................................................................................38

VIII.

Irodalomjegyzék .......................................................................................................39

I.

Egy-két szó a sudokuról

A sudoku (japánul 数独) egy logikai játék, melyben megadott szabályok szerint számjegyeket kell elhelyezni egy táblázatban. A „sudoku” név egy hosszabb japán kifejezés rövidítése. Az eredeti név jelentése: „a számjegyek csak egyszer szerepelhetnek” (数字は独身に限る, szúdzsi va dokusin ni kagiru). Ez a japán Nikoli Co. Ltd. bejegyzett védjegye. A megoldott sudoku egy speciális latin négyzet. Latin négyzetekkel kapcsolatos munkássága miatt sokan úgy tartják, a játék ötlete Leonhard Eulertől származik. A játék ma ismert változatát az amerikai Howard Garns alkotta meg 1979-ben. A rejtvényt a Dell Magazines adta ki Number Place címmel. A játék 1986-ban nagy népszerűségre tett szert Japánban, mikor a Nikoli kiadta a játék japán változatát. A nemzetközi siker 2005-ben érkezett el. A sudoku meglepően egyszerű szabályokon alapul – igazán nem az a fajta rejtvény, amiről azt gondolnánk, hogy álmatlan éjszakákat okoz. Egy 9 x 9 négyzetből álló nagy négyzetben kell elhelyezni a számokat 1-től 9-ig úgy, hogy egy tetszőleges sorban, oszlopban és háromszor hármas négyzetben mindegyik szám csupán egyszer forduljon elő. Segítségül bizonyos számokat előre megadnak. A sudokunak vannak speciális fajtái (sudoku X, 3D sudoku ill. mini- és óriássudoku), de én csak a szokásos 9 x 9 –es táblára mutatok megoldási heurisztikákat.

3

II.

Felhasználói dokumentáció

Program célja A program célja, hogy bemutassa a backtrack algoritmus használatával sudoku fealdványok megoldását.

Hardver-szoftver követelmények Szoftver: A program Microsoft .NET 4.0 környezetet igényel. Tesztelt operációs rendszerek: 

Microsoft Windows 7

Hardver: A futtatáshoz az operációs rendszer és a futóprogramok hardverigényén felül a programnak 24 MB RAM szükséges.

Telepítés Ha már a szükséges Frameworköt telepítése után maga a program telepítést nem igényel.

A program részei 

sudoku.exe



Cursors (Mappa)



Tables (Mappa)

A program használata Indítsuk el a sudoku.exe –t. A következő ablak jelenik meg előttünk:

4

Ablak elemei Start Elindítja a betöltött feladat megoldását a kiválasztott heurisztikával. Clear Minden mező tartalmát törli. Reset Csak a nem lefixált mezők tartalmát törli. Exit Kilép a programból. Heruistic type Itt lehet kiválasztani a heurisztikát. A három lehetőségről bővebben a heurisztikáknál olvasható. Add field Van lehetőség saját feladvány generálásra. Az Add Field gomb nem csinál mást mint hozzáad egy olyan mezőt a táblához amely nem sérti a többi mezőt.

5

Generate Generál egy saját sudoku táblát a kiválaszott heurisztikával. Speed Itt állítható be a megoldás sebessége. Find all solution A feladvány összes lehetséges megoldásának megkeresése. Backtrack number Visszalépések száma. Információs sáv A program jobb felső részén kapott helyett az információs sáv, ahol a futással kapcsolatos információkat olvashatjuk.

Menü elemei File



Open: feladvány megnyitása



Save: aktuális feladvány mentése



Exit: kilépés

Options

6



Flash chechked fields: felvillantja az éppen vizsgált mezőket. (Jóval hosszabb lesz a feladvány megoldásának ideje.)

Find all solutions megoldásainak megtekintése A példában 3 megoldást talált a program az adott feladványra.

1. megoldás

2. megoldás

7

A megoldások között lapozgatva narancsságra színnel kiemeli a két megoldás közötti különbséget.

8

III. Fejlesztői dokumentáció

Model Detail This document provides a complete overview of all element details. For simpler and more focused reports, simply copy this initial template and turn off the sections not required.

Class Model Type: Status: Package: Detail: GUID:

Package Proposed. Version . Phase 1.0. Model Created on 2011.05.08.. Last modified on 2011.05.08. {5E6E7146-EE7E-4ecd-BD41-347B113EDBCB}

SudokuWPF Type: Status: Package: Detail: GUID:

Package Proposed. Version 1.0. Phase 1.0. Class Model Created on 2011.05.08.. Last modified on 2011.05.08. {2476C53C-81AB-4b53-8E4B-CBE1B8452CCE}

App Type: Status: Package: Detail: GUID:

Class Application Proposed. Version 1.0. Phase 1.0. SudokuWPF Keywords: Created on 2011.05.08.. Last modified on 2011.05.08.. {9C465D8C-642F-47ff-AAD3-400E8036691A}

Interaction logic for App.xaml

Custom Properties  isActive = False

Tagged Values  partial = true.

BestPositionHeuristic Type: Status: Package: Detail: GUID:

Class Heruistic Proposed. Version 1.0. Phase 1.0. SudokuWPF Keywords: Created on 2011.05.08.. Last modified on 2011.05.08.. {5109115E-D61D-481c-A6DE-2BD02BC81BE8}

9

Legjobb poziciót kihasználó huerisztika.


Connections Connector Generalization Source -> Destination

Attributes Attribute goodNumbers HashSet Public

Operations Method BestPositionHeuristic() Public fillField() bool Private

Source Public BestPositionHeuristic

Target Public Heruistic

Notes

Notes Azokat a számok melyek még megoldások lehetnek egy adott helyre.

Constraints and tags Default: new HashSet { 1, 2, 3, 4, 5, 6, 7, 8, 9 }

Notes Konstruktor.

Parameters SudokuC [in] _sudokuTable

Mező kitöltése értékkel.

HashSet [in] goodNumbers int [in] szam int [in] backTrackNum

getBestField() int Private

Legkevesebb számmal kitölthető mező megkeresése.

getDobozHeur() HashSet Private

GoodNumbers tömbből eltávolítja azokat a számokat amik az adott doboz miatt kizáródnak.

HashSet [in] goodNumbers

getOszolopHeur() HashSet Private

GoodNumbers tömbből eltávolítja azokat a számokat amik az adott oszlop miatt kizáródnak.


getSorHeur() HashSet Private

GoodNumbers tömbből eltávolítja azokat a számokat amik az adott sor miatt kizáródnak.


Run() State Public setGoodNumbersSet() void Private

Feladvány megoldásának indítása.

int [in] szam

int [in] szam

int [in] szam

Lehetségesk számok tömbjéből a kizárt számok int [in] i eltávolítása.

10

FromIndexHeuristic Type: Status: Package: Detail: GUID:

Class Heruistic Proposed. Version 1.0. Phase 1.0. SudokuWPF Keywords: Created on 2011.05.08.. Last modified on 2011.05.08.. {26003B61-98EF-4155-9372-E02BAE22D05D}

Sorfolytonos heurisztika.


Connections Connector Generalization Source -> Destination Generalization Source -> Destination

Operations Method FromIndexHeuristic() Public

Source Public RandomIndexHeuristic

Target Public FromIndexHeuristic

Public FromIndexHeuristic

Public Heruistic

Notes Konstrukor.

Notes


Feladvány megoldásának indítása.

Run() State Public SetIndex() void Public

Kezdeti index beállítása.

Heruistic Type: Status: Package: Detail: GUID:

Class Proposed. Version 1.0. Phase 1.0. SudokuWPF Keywords: Created on 2011.05.08.. Last modified on 2011.05.08.. {13FDA691-E200-4fae-9B3A-0D2284A9AA39}

Absztakt heurisztika osztály.


Connections Connector

Source

Target

11

Notes

Connector Association Source -> Destination

Source Public SudokuC

Target Public heuristic Heruistic

Generalization Source -> Destination

Public FromIndexHeuristic

Public Heruistic

Generalization Source -> Destination

Public BestPositionHeuristic

Public Heruistic

Association Source -> Destination

Public Heruistic

Protected way Way


Public Heruistic

Protected sudokuTable SudokuC


Public Heruistic

Public state State

Attributes Attribute actfield int Protected

Notes

Notes Aktuális mező.

Constraints and tags Default:

backColor Brush Public

Visszalépés színe.

Default: Brushes.Red

cycleTime TimeSpan Public

Ciklus idő.

Default:

flashNotOk Brush Public

Szabályt sértő szám találásának jelzése.

Default: Brushes.PaleVioletRed

flashOk Brush Public

Szabályokat nem sértő szám találásának jelzése.

Default: Brushes.YellowGreen

forwardColor Brush Public

Előrelépés színe.

Default: Brushes.LightGreen

Index int Protected

Index tömb.

Default: new int[81]

Utolsó ciklus végének időpontja.

Default:

lastModField int Protected

Utolsó módosított mező.

Default:

state State Public

Állapot.

Default:

sudokuTable SudokuC Protected

Sudoku tábla.

Default:

wait int Protected

Várakozás.

Default:

Collection lastCycleEndTime DateTime Public

12

Attribute

Notes

Constraints and tags

way Way Protected

Irány.

Default:

Operations Method DobozCsekk() bool Public

Notes Egy mezőre megvizsgálja, hogy a tartalma megfelel-e az adott négyzetnek.

Parameters int [in] szam

OszlopCsekk() bool Public

Egy mezőre megvizsgálja, hogy a tartalma megfelel-e az adott oszlopnak.

int [in] szam

Pause() void Public Run() State Public SaveSolution() void Public setWait() void Public

Pause.

Várakozás beállítása

int [in] time

SorCsekk() bool Public

Egy mezőre megvizsgálja, hogy a tartalma megfelel-e az adott sornak.

int [in] szam

UtkozesCsekk() bool Public

Egy mezőre megvizsgálja, hogy a tartalma szabályos-e.

int [in] szam

Futtatás. Megoldás elmentése.

Way Type: Status: Package: Detail: GUID:

Enumeration Proposed. Version 1.0. Phase 1.0. SudokuWPF Keywords: Created on 2011.05.08.. Last modified on 2011.05.08.. {EABA573A-9A34-4b0a-949E-E57F9F4D71A9}

Irány enum.


Connections Connector Association Source -> Destination

Attributes Attribute

Source Public Heruistic

Target Protected way Way

Notes

Notes


Right Public

13

Attribute

Notes


Left Public

HeruisticEnum Type: Status: Package: Detail: GUID:

Enumeration Proposed. Version 1.0. Phase 1.0. SudokuWPF Keywords: Created on 2011.05.08.. Last modified on 2011.05.08.. {5A8EE6CC-A96D-4c33-A841-9C0B20890086}

Heurisztikák.





Target Public heur HeruisticEnum

Notes

Notes


FromIndex Public RandomIndex Public

Default:

BestPos Public

Default:

RandomIndexHeuristic Type: Status: Package: Detail: GUID:

Class FromIndexHeuristic Proposed. Version 1.0. Phase 1.0. SudokuWPF Keywords: Created on 2011.05.08.. Last modified on 2011.05.08.. {4C3A485B-1D35-43be-A015-54F3020FA36F}

Véletlen indexű heurisztika.

Custom Properties

14


Connections Connector Generalization Source -> Destination

Source Public RandomIndexHeuristic

Target Public FromIndexHeuristic

Operations Method Notes RandomIndexHeuristic() Konstruktor. Public

Notes


Véletlen indexek beállítása.

SetIndex() void Public

Solution Type: Status: Package: Detail: GUID:

Class Proposed. Version 1.0. Phase 1.0. SudokuWPF Keywords: Created on 2011.05.08.. Last modified on 2011.05.08.. {E120B57F-0DEB-4f2c-A011-6FAB4E956D34}

Megoldás.



Notes


Fixált mezők tömb.

Default: new bool[81]

Collection numbers string Public

Számok tárolása.

Default: new string[81]

Collection solNumber int Public

Megoldások száma.

Default:

Notes Konstruktor

Parameters string[] [in] _numbers

isFixed bool Public

Operations Method Solution() Public

bool[] [in] _isFixed

15

Method

Notes

Parameters int [in] _solNumber

State Type: Status: Package: Detail: GUID:

Enumeration Proposed. Version 1.0. Phase 1.0. SudokuWPF Keywords: Created on 2011.05.08.. Last modified on 2011.05.08.. {202F5BA4-4F01-48b9-ADF2-935BCFA987F2}

Megoldás állapota.




Target Public state State


Public Heruistic

Public state State


Notes

Notes


NotValidInput Public

Default:

Complete Public

Default:

Running Public

Default:

Stopped Public

Default:

FindSolution Public

Default:

GenerateRunning Public

Default:

Find2Solutoins Public

Default:

GenerateComplete Public

Default:

16

Attribute

Notes


Default:

GenerateStop Public

SudokuC Type: Status: Package: Detail: GUID:

Class Proposed. Version 1.0. Phase 1.0. SudokuWPF Keywords: Created on 2011.05.08.. Last modified on 2011.05.08.. {D867F63C-0CE3-4003-8786-CD1ABE99EB36}



Source Public sudokuWindow

Target Private sudoku SudokuC


Public SudokuField

Private parent SudokuC


Public SudokuC

Public sudokuFields SudokuField


Public SudokuC

Public state State


Public SudokuC

Public parentWindow sudokuWindow


Public SudokuC

Public heuristic Heruistic


Public SudokuC

Public heur HeruisticEnum


Public Heruistic

Protected sudokuTable SudokuC

Attributes Attribute backTrackNumber int Public

Notes

Notes


Visszalépések száma

Default:

17

Attribute

Notes

changeSolutionColor Brush Private finishTime string Public

Megoldások lapozgatása közbenni különbségek Default: Brushes.Orange kiemelése szín. Megoldás ideje.

Default:

heur HeruisticEnum Public

Heurisztika enum.

Default:

heuristic Heruistic Public

Heurisztika.

Default:

isfindAllSolutionCheckB ox bool Public

Be van-e pipálva az összes megoldás megkeresése?

Default:

isFixed bool Public

Fixált mezők.

Default: new bool[81]

Be van-e állítva a villantás?

Default: true

isPaused bool Public

Pause-olva van-e a megoldás?

Default: false

isStopped bool Public

Le van-e állítva a megoldás?

Default:

lastModField int Public

Utoljára módosított mező indexe.

Default: -1

Collection isFlash bool Public


lastModFieldColor Brush Utoljára módosított mező színe. Public

Default:

lastTime DateTime Public

Default:

maxSolutonsNumber int Public

Maximum megoldások száma.

Default: 0

maxWait int Public

Maximum várakozási idő.

Default: 2000

numbers string Public

Számok tömb.

Default: new string[81]

Szülő ablak.

Default:

Processz idő.

Default: true

Collection parentWindow sudokuWindow Public processTime bool Public rand Random Private

Default:

runTime TimeSpan

Default:

18

Attribute

Notes


showPos bool Public

Mutassa az aktuális pozicíó.

Default: true

solutionNumber int Public

Megoldások száma.

Default:

solutionsList List<Solution> Public

Megoldások listája.

Default: new List<Solution>()

startDate DateTime Private

Elindítás ideje.

Default:

state State Public

Állapot.

Default:

Private

sudokuFields SudokuField Sudoku tábla mezői. Public

Default: new SudokuField[81]

Collection

wait int Public

Operations Method AddGenerateField() void Public changeActiveSudokuFiel d() void Public ClearTable() void Public FieldsToNumbers() void Public FindDifferenceTwoSoluti on() void Public

findSolution() void Public Flash() void Public

Várakozási idő.

Default: 0

Notes Új mező generálása.

Parameters

Mezőváltás.

int [in] num

Tábla teljes törlése. Mezők értékének betöltése a numbers tömbbe. Két megoldás közötti különbség beállítása.

int [in] a int [in] b

Megoldás találat. A vizsgált részt felvillantja.

List [in] array Brush [in] color

GenerateTable() void Public

Új tábla generálása.

byte [in] needFilledField int [in] _maxSolutonsNumber

Get() string Public

Mező értékének lekérése.

19

int [in] number

Method

Notes

Parameters

GetFromAllSolutionChec kbox() bool Public GetFromIndexComboVal ue() string Public getSolutionNumber() string Public GetSudokuField() string Public

All solution be van-e pipálva?

GetSudokuFieldsToForm () void Public GetSudokuFieldsToForm 2() void Public GetTime() string Public IsValidInput() bool Public LockTable() void Public ResetTable() void Public Run() void Public RunGenerate() void Public Set() void Public

Numbers tömb tartalmának kiírása a táblára. (Generáláshoz szükséges)

Combobox aktuális értékének lekérése. Megoldások számának lekérése. Mező értékének lekérése típus függvényében.

Numbers tömb tartalmának kiírása a táblára. (SetSudokuTableFromSolution szükséges)

int [in] number

Solution [in] sol

Idő lekérése. Megoldható-e az input? Tábla lezárása. Tábla törlése, fixált mezők megtartásásval. Start gomb onclick. Új tábla generálása. Mező értékének beállítása.

int [in] number string [in] text

SetBackColor() void Public

Mező hátterének beállítása.

int [in] number Brush [in] color

int [in] number

SetBackColorDelegate() void Public

SetSudokuField() void Public

Brush [in] color Mező értékének beállítása.

int [in] number string [in] value

SetSudokuTableFromSol Megoldás betöltése a táblára. ution() void Public setWaitTime() void Várkozó idő beállítása. Public startTimer() void Private

Időzítő inditása.

20

Solution [in] sol

int [in] time

Method SudokuC() Public

Notes Tábla generálása.

UnlockTable() void Public

Tábla feloldása.

Parameters sudokuWindow [in] _parentWindow

SudokuField Type: Status: Package: Detail: GUID:

Class System.Windows.Controls.TextBox Proposed. Version 1.0. Phase 1.0. SudokuWPF Keywords: Created on 2011.05.08.. Last modified on 2011.05.08.. {4278D8B3-E424-4e3d-8257-3066516A78D8}

Sudoku mező.


Connections Connector Association Source -> Destination Association Source -> Destination

Attributes Attribute isLocked bool Private

Source Public SudokuField

Target Private parent SudokuC

Public SudokuC

Public sudokuFields SudokuField

Notes

Notes Lezárt mező?

Constraints and tags Default: false

myIndex int Private

Mező indexe.

Default:

parent SudokuC Private

Szülő objektum.

Default:

Notes Mező törlése.

Parameters

Operations Method ClearField() void Public Lock() void Public mouseEnterSudokuField( ) void Private

Mező lezárása. Kurzor lecserélése.

object [in] sender MouseEventArgs [in] e

21

Method

Notes

Parameters

ResetField() void Mező törlése, ha nem fixált. Public SetFieldBackColor() void Mező háttérszínének beállítása. Private

object [in] sender EventArgs [in] e

Konstruktor.

SudokuField() Public

int [in] xPos int [in] yPos int [in] _index SudokuC [in] _parent

SudokuField_GotFocus() Fókusz megkapása. void Private

object [in] sender

SudokuField_LostFocus() Fókusz elvesztése. void Private

object [in] sender

SudokuFieldPKeyDown() Billentyű nyomás kezelése. void Private

Object [in] sender

RoutedEventArgs [in] e


Mező feloldása.

Unlock() void Public

settingsWindow Type: Status: Package: Detail: GUID:

Class Window Proposed. Version 1.0. Phase 1.0. SudokuWPF Keywords: Created on 2011.05.08.. Last modified on 2011.05.08.. {F170F14F-25BB-44d6-8A1A-8E28E1B4A516}

Interaction logic for settingsWindow.xaml



22

KeyEventArgs [in] e

Operations Method settingsWindow() Public

Notes

Parameters

sudokuWindow Type: Status: Package: Detail: GUID:

Class Window Proposed. Version 1.0. Phase 1.0. SudokuWPF Keywords: Created on 2011.05.08.. Last modified on 2011.05.08.. {A202E3D8-BF96-4b5d-8A52-D50F5C9B255E}

Interaction logic for Window1.xaml



Connections Connector Association Source -> Destination Association Source -> Destination

Attributes Attribute cur Cursor Public

Source Public sudokuWindow

Target Private sudoku SudokuC

Public SudokuC

Public parentWindow sudokuWindow

Notes

Notes

Constraints and tags Default: new Cursor(Environment.CurrentDirecto ry.ToString() + "\\Cursors\\pencil.cur")

findAllSol bool Private

Default: false

fromIndexComboVal string Private

Default: "0"

lastModField int Private

Default: -1

lastSolNum int Private

Default: 0

23

Attribute

Notes


mainTimer System.Timers.Timer Private

Default:

openFile OpenFileDialog Private

Default:

runThread Thread Private

Default:

saveFile SaveFileDialog Private

Default:

sudoku SudokuC Private

Default:

Operations Method addFieldButton_Click() void Private

CheckedChanged() void Private

Notes

Parameters object [in] sender RoutedEventArgs [in] e

Heurisztikaváltás.


clearButton_Click() void Private


exitButton_Click() void Private

object [in] sender RoutedEventArgs [in] e

findAllSolClick() void Private


fromIndexCombo_Select edIndexChanged() void Private

object [in] sender

generateButton_Click() void Private

object [in] sender

EventArgs [in] e


GetFindAllSolutionComb o() bool Public GetFromIndexComboVal Combobox indexének lekérése.

24

Method ue() string Public leftButton_Click() void Private

Notes

Parameters

Előző megoldás betöltése.


LoadFromFile() void Private

Fájlból betöltés.

LockButtons() void Public mainTimer_Tick() void Private

Gombok lezárása.

string [in]

Főidőzítő.


openToolStripMenuItem _Click() void Private

object [in] sender

pauseButton_Click() void Private

object [in] sender

EventArgs [in] e


resetButton_Click() void Private


rightButton_Click() void Private

Követlező megoldás betöltése.


SaveToFile() void Private

Mentés fájlba.

string [in]

object [in] sender

saveToolStripMenuItem_ Click() void Private

EventArgs [in] e

SetArrowButtonsEnabled Megoldás nyilak engedélyezése / tiltása. () void Private SetFieldsToWhite() void Tábla befehérítése. Private solutionKeyDown() void Private

object [in] sender KeyEventArgs [in] e

speedBar_Scroll() void Private

Sebesség szövegének módosítása speedbar értéke alapján.


25

Method

Notes

Parameters

startClick() void Private


sudokuWindow() Public tableName_GotMouseCa Táble nevének beállítása. pture() void Private

object [in] sender MouseEventArgs [in] e

tableName_KeyDown() void Private

object [in] sender

tablePlace_MouseEnter() void Private

object [in] sender

KeyEventArgs [in] e

MouseEventArgs [in] e

UnlockButtons() void Gombok feloldása. Public UnlockButtonsDelegate() void Private Window_Closing() void Ablak bezárásakor a futó szál abortálása. Private

object [in] sender System.ComponentModel.Cancel EventArgs [in] e

Window_KeyDown() void Private

object [in] sender KeyEventArgs [in] e

26

Rejtvény mentése fájlba

A rejtvény a követekező formában van tárolva: Fájl neve: extreme.xml Fájl tartalma: Extreme 9 7 4 8 7

27

2 1 9 7 2 4 6 4

28

1 5 9 9 8 3 8 3 2

29

6 2 7 5 9

Backtrack algoritmus a sudoku táblán A heurisztikák működése nagyon hasonló, csupán abban térnek el, hogy máshogy választják meg a mezők sorrendjét (ez nagyon apró különbségnek tűnhet, de mégis nagy mértékben befolyásolja a program futási idejét). A sorfolytonos (FromIndex) heurisztika működése (a kiválasztott indextől indul az algoritmus, az egyszerűség kedvéért legyen ez a bal felső sarok): Az aktuális mezőt kitölti a lehető legkisebb értékű a szabályokat nem sértő számmal a megengedett tartományon (1-9 között). Előre lépés következik, a következő mezőre áll és azt is hasonlóan kitölti. Előre lépések esetén egyszer csak eljutunk a (9,9) 81-es indexű mező utáni mezőre, „lemennék” a tábláról, ekkor találtunk egy megoldást a feladványra. Abban az esetben, ha egy mezőre nem találunk szabályt nem sértő számot, akkor visszalépés történik. Azaz az előző mezőre lép vissza és megkeresi a következő lehetséges legkisebb számot. Amikor visszalépések során a kezdő indexű mező helyére már a 9-es sem elfogadható, tehát visszalépés történik, de kiindexelnénk a tömbből, ekkor a feladvány nem megoldható (Not a valid input). 30

Find all solutions Abban az esetben, ha a tábla összes lehetséges megoldását megkívánjuk találni nem kell mást tennünk, mint: Megoldás találata esetén elmenteni a tábla aktuális állását és folytatni az algoritmust egészen addig amíg vissza nem jutunk a kezdőmezőre és visszalépés történik. Ebben az esetben ez csupán annyit jelent, hogy nincsen több megoldás. Rossz input akkor van, ha a megoldások száma nulla.

Példa egy visszalépésre

1. lépés - (1,1) mező: 1-es ki lett zárva az oszlop miatt, 2-es a legkisebb szám ami nem ütközik semmivel 2. lépés – (2,1) mező: 1-es ki lett zárva az oszlop miatt, 2-es ki lett zárva sor miatt, a 3as legkisebb szám ami nem ütközik semmivel 3. – 5. lépés hasonlóan mint az előzőek. 6. lépés (7,1) mező: Sor miatt ki lettek zárva: 1, 2, 3, 4, 5, 7, 9 Oszlop miatt ki lettek zárva: 4, 6, 8 Doboz miatt ki lettek zárva: 4, 6, 7, 8, 9 goodNumbers tömb tartalma: { } 31

Visszalépés történik, álljunk rá az előző mezőre. 7. lépés (6,1) mező: mező értékének kiolvasása, majd növelése 1-el és az új érték ütközésvizsgálata.

Tábla generálása Program lehetőséget nyújt saját feladvány generálására. Generálás lépései a következők: 1. lépés: 12 véletlenszerű mező kitöltése úgy, hogy ne legyen ütközés 2. lépés: Add field (új véletlenszerű ütközésmentes mező hozzáadása a táblához) 3. lépés: Ha a megoldások száma kisebb, mint 4 készen vagyunk, amúgy ugrás 2. lépésre

32

IV. Heurisztikák Heurisztika jelentése: a feltalálás módja, az alkotó tevékenység módszereinek tudománya

A program minden egyes megoldásnál backtrack algoritmust használ. Nézzük meg sorrendben a használt heurisztikákat.

Sorfolytonos (From index) Adott indextől indulva sorfolytonosan halad végig a mezőkön, ha olyan mezőhöz ér ahonnan mind a kilenc szám tiltott, akkor visszalép. Közepesen gyors heurisztika.

Legjobb pozíció (Best position) Első körben megkeresi, hogy melyik mezőben fordulhat elő a lehető legkevesebb lehetőség. Utána ezt a mezőt kitölti, és újra keresi következő mezőt. A három heurisztikából a leggyorsabb. 33

Véletlen pozíció (Random index) Az sorfolytonos heurisztika egy indextömb alkalmazásával. Megoldásra jut, de a megoldás ideje csak is azon múlik, hogy az indextömb és adott feladvány mennyire „passzolnak” egymáshoz. A valóságban nem használható sudoku tábla megoldására, inkább csak a másik két heurisztika megerősítésére szolgál.

34

V.

Tesztelési terv és statisztikák

Tesztelési terv Rossz input Két féle rossz input létezik: 

Elején meg lehet állapítani: a megadott input nem felel meg a sudoku szabályainak. Ugyan olyan szám szerepel egy sorban, oszlopban vagy négyzetben. Erre az esetre van egy eljárás amely indításkor megnézni, hogy az adott input helyes-e, ha nem helyes leállítja a megoldást.



Elején nem lehet megállapítani: ebben az esetben nem lehet „ránézésre” megmondani, hogy az adott input nem megoldható. Az algoritmus idővel fel fogja tárni, hogy nem létezik az inputnak megoldása.

Üres input Üres táblát bármelyik heurisztika megoldja. Normál input Bármely megoldható inputot mind a három heurisztika hibátlanul megoldja.

Statisztikák Tesztelés a következő gépen történt Operációs rendszer: Windows 7 professional (32 bit) Processzor: Intel(R) Core (TM) 2 Duo CPU E8500 @ 3.16 GHz 3.17GHz Memória: 2 GB

35

Eredmények A programot nyomtatásban megjelent és internetes forrásból származó sudoku feladványokkal teszteltem. A feladatok osztályozva vannak a készítő által. A tesztek alatt arra voltam kíváncsi, hogy a különböző nehézségű rejtvények megoldása különböző heurisztikákkal mennyi idő alatt valósítható meg. Best position Első megoldás Tábla neve

megtalálása Idő


Összes megoldás megtalálása Visszalépések

Idő

száma

Megoldások száma

Easy

100 ms

265

350 ms

1207

18

Standard

65 ms

117

140 ms

364

3

Extreme

25 ms

49

40 ms

103

1

From index Első megoldás Tábla neve

megtalálása Idő


Összes megoldás megtalálása Visszalépések

Idő

száma

Megoldások száma

Easy

10 ms

283

1.1 s

52293

18

Standard

120 ms

4758

130 ms

5248

3

Extreme

300 ms

13474

500 ms

23501

1

Ramdom index: Minden egyes program futtatás esetén más, így nem lehet statisztikát készíteni erről a heurisztikáról.

36

VI. Fejlesztési

lehetőségek,

forráskód

és

dokumentáció Fejlesztési lehetőségek A program úgy lett felépítve, hogy további heurisztikákkal könnyen bővíthető legyen. Ehhez a Heuristic osztályból kell származtatni egy alosztályt.

Forráskód és dokumentáció A program Microsoft Visual Studio 2010 alatt készült C# nyelven. A teljes forráskód a mellékelt CD-n található meg. A dokumentáció Enterprise Architect és Microsoft Word segítségével készült.

37

VII. Összefoglalás Kezdetben csak magamat állítottam próba elé egy sudoku megoldó program elkészítésével, később választottam szakdolgozatom témájának. Szakdolgozatom elkészítésével szerettem volna bemutatni a backtrack algoritmus működését, amit a megoldási sebesség csúszka segítségével úgy érzem sikerült megvalósítani. Ezek után gondolkodtam el más heurisztikák implementálásában (Best position és Random index), melyek remekül bemutatják, hogy egy adott tábla megoldásánál mennyire fontos a megoldási mezők sorrendjének meghatározása. Aztán láttam meg a lehetőséget, hogy e technikák használatával saját feladvány generátor is megvalósítható.

38

VIII. Irodalomjegyzék [1] http://hu.wikipedia.org/wiki/Sz%C3%BAdoku 2011 [2] http://en.wikipedia.org/wiki/Sudoku 2010 [3] http://www.sudopedia.org/wiki/Main_Page 2011 [4] http://www.websudoku.com 2011

39

Eötvös Loránd Tudományegyetem. Informatikai Kar. Média- és Oktatásinformatika Tanszék. Sudoku megoldó. programozó matematikus szak

Recommend Documents