Sudoku problem

English flag During last week in our office there were some discussions about algoritms leading to resolving of sudoku. Some colegues proposed brute force algoritm and started to implement it in Java with no success. They tried to generate all combinations for possible row/column vector. They finished with OutOfMemory error.
Well my idea was to find solution by simulation human being. I just reminded myself how I resolve sudoku in newspaper. The way is pretty simlpe. In the first step I always evaluate each field of sudoku desc and fill in fields where only single value can be filled. Then for other fields I write list of possible values to the corner of the field and in each iteration I elide impossible values.
That works and leads to solution, so I implemented this algoritm. But there are some limitations of this approach. In case there exist many different results the execution time is too long and may lead to OutOfMemory as well. The marginal example is empty input sudoku desc where we don't have a field with known value.
I found some improvements which I didn't use in my code. I will show you following 2 examples that may speed up the execution time:

1.The following rule is valid for line, column or square. If there exist line where a value is possible to fill only to one of all line fields then file such number in. In the following sample number 1 will be filled in 4th field from the left.
sudoku

2.This is similar to previous rule. In line highlighted by red there must be following numbers: 1,2,3. So there will be number 1 in the left or in the right field therefore we can exclude it from middle field and file in 3 there in the middle field of this line.
sudoku

I expect there are many other simple rules that can be applied. But I don't want to study this problematic deeper. I even don't want to read some studies related to sudoku (I expect there exist many resources in the internet). My intension was to code sudoku solver quickly (although it was not so quicksmile) and you can download result of my work here.
Czech flag Během minulého týdne probíhaly v naší kanceláři diskuse o algoritmech vedoucích k řešení sudoku. Kolegové navrhli brute force algoritmus a pokusili se jej implementovat v jazyce Java, ovšem neúspěšně. Zkusili generovat všechny kombinace pro vektory řádků/sloupců. Jejich snaha byla ukončena v důsledku OutOfMemory error.
Moje myšlenka na nalezení řešení směřovala přes simulaci chování člověka. Připomněl jsme si, jak řeším sudoku na papíře. Tato cesta je poměrně jednoduchá. V prvním kroku si vždy ohodnotím všechna políčka desky sudoku a vyplním ta políčka, do kterých lze dosadit jedinou hodnotu. Pak si ke všem ostatním políčkům zapíši všechny možné hodnoty a při každé iteraci vyškrtnu hodnoty nevyhovující.
Tato metoda funguje a vede k řešení, takže jsem algoritmus naimplementoval. Jsou zde ale jistá omezení. Tento přístup může vést ke zdlouhavému výpočtu a také OutOfMemory. Mezním příkladem je deska sudoku, na které není jako vstup vyplněno ani jedno políčko.
Přišel jsem ještě na vylepšení, která jsem ovšem nepoužil ve zdrojovém kódu. Následující 2 příklady mohou urychlit doby výpočtu:

1.Následující pravidlo je platné pro řádek, sloupec a taky pro čtverec sudoku. Pokud existuje řádka, na kterou je možné vyplnit některou hodnotu pouze do jednoho políčka, pak toto číslo vyplníme. V následujícím příkladu se do 4. políčka zleva zapíše číslo 1.
sudoku

2.Toto pravidlo je obdobou předchozího. Na řádku zvýrazněnou červeně se musí zapsat hodnoty 1,2,3. Přičemž 1 musí být buď v levém nebo v pravém políčku. Takže uprostřed musí logicky být 3.
sudoku

Očekávám, že existuje více takto jednoduchých pravidel. Já ovšem nebudu tuto problematiku studovat do hloubky. Nechci ani číst žádné studie týkající se sudoku (tipnul bych si, že na internetu je možné najít spoustu odkazů). Mým cílem bylo vyřešit sudoku rychle (ikdyž to až tak rychle nebylo smile). Výsledek mého snažení v podobě NetBeans projektu si můžete stáhnout zde.
Comments:

I wrote a simple Soduku solver in Java by creating a SodukuSet object that performed simple eliminations based on known cell values. Then I assigned each row, column and box a SodukuSet. This worked really well for simple puzzles. I was also able to apply several other "rules" to either find a cell value, or eliminate values from a cell.

It was then that I learned that I didn't understand some of the more complicated elinimation algorithms. The best site that I found for solving puzzles, and explain what it's doing step by step, is this site:

http://www.scanraid.com/sudoku.htm

Posted by Kevin on květen 28, 2006 at 08:31 odp. CEST #

Jaro, it works ;)
Don't publish nbproject\\private directory in your project. It has no sense and can cause problems.
When I looked into your code I remembered that it's good to publish source code under a licence (even in case when you want eveybody let to do whatever with the code)

Posted by Lukas on květen 31, 2006 at 05:14 dop. CEST #

Post a Comment:
  • HTML Syntax: NOT allowed
About

jara

Search

Archives
« duben 2014
PoÚtStČtSoNe
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
    
       
Today