Neděle V 28, 2006

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.

Středa V 17, 2006

Java will be opensource

English flag Will Java be opensourced? That was very often discussed question in the past. Now we have answer of Rich Green. At JavaOne Conference 2006 he stated that the question is not whether or not but how to do it (according to zive.cz article - in Czech). I hope opensourcing Java would help Java to gain more users and the world would be more perfect with more and more java software, devices... But, we have to wait whether, when and how will Java be opensourced.
Czech flag Bude Java opensourcovaná? Tak to je otázka, která byla v minulosti velice často diskutovaná. Nyní ale máme odpověď od Riche Greena. Ten během Konference JavaOne 2006 uvedl, že v tuto chvíli není otázka zdali ale jak to provést (podle článku na zive.cz). Doufám že opensourcování by Javě mohlo přinést více uživatelů a svět by mohl být lepší s více a více Java aplikacemi, zařízeními... Musíme si ale počkat na to jestli, kdy a jak bude Java opesourcována.

Úterý III 14, 2006

JFreeChart - generujeme grafy v jazyce Java / JFreeChart - generate charts in Java

Czech flag NetBeans Quality Engineering ukazuje na svých stránkách grafy týkající se kvality produktu.
Pie chart
Ne náhodou se pro jejich generování používá JFreeChart. Tato velmi užitečná knihovna je k mání už řadu let. Mezi nesporné výhody patří:
  • je zdarma
  • je psaná v jayzce Java, takže ji můžete použít na jakékoliv platformě
  • je to opensource GNU Lesser General Public Licence
  • podporuje přímý export jako .png a .jpg
Jednu výtku bych přeci jen k této knihovně měl. Týká se kompatibility verzí. Přecházel jsem totiž kdysi z jedné verze na novější. To ale vyžadovalo velké zásahy do mého kódu - spousta změn i tam kde byste to vůbec nečekali. Potřeboval jsem ovšem vylepšení obsažené v nové verzi, takže jsem tuto překážku překonal. Od té doby si vystačím s verzí 0.9.2 (dnes je aktuální verze 1.0.1).
English flag NetBeans Quality Engineering has on pages charts related to the product quality.
Pie chart
JFreeChart is used for generation of these charts. This very useful library is available for a couple of years. The main advantages are: Well it has also one disadvantage related to compatibility of versions. Once I needed to upgrade to a new version. The upgrade required big changes in my code - even there where you wouldn't expected. But I needed the improvements or features included in new version so I fetched through these barriers. Since then I am happy with version 0.9.2 (actual version today is 1.0.1).

Pátek III 10, 2006

Java test

Czech flag Dnes mě jeden můj kolega vyzkoušel jednoduchým příkladem z programátorských dovedností. Musím se přiznat, že jsem neodpověděl správně. Jsem znechucený a budu celý víkend studovat. Uhádnete aspoň vy, co vypíše následující kousek kódu?
Source code
English flag One of my colegues gave me a quick test from Java skills today. He asked me just an easy question. Unfortunately I have to say I failed. I am frustrated and thus I will study whole weekend. So you can check your skills on the same test. What is the result of the following code?
Source code

Středa III 08, 2006

Java Runtime Environment Version 5.0 Update 6

Czech flag Stáhněte si nový update JRE. Objevil se na stránkách java.com. Všimnul jsem si tam jedné zajímavé informace a sice že počet zařízení s java technologií je více než 2,5 miliardy. Pokud nechcete zaostávat, tak si stáhněte Java Software kliknutím na následující banner:
English flag Download new update of JRE. It appeared on pages of java.com. I noticed one interesting information there Java powers more than 2.5 billion devices. If you want to keep up download Java Software by clicking on following banner:

Čtvrtek II 23, 2006

Přehrávejte mp3 v Javě / Play mp3 in Java

Czech flag Patřím k nevelké skupině počítačových uživatelů, kteří pracují s Mac OS X. Na tomto systému jsem se nedávno setkal s performance problémem, kdy integrovaný přehrávač hudby iTunes začal polykat stále více zdrojů. Tento problém jsem vyřešil poměrně neobvykle. Sáhnul jsem totiž po opensource produktu, který mi iTunes dokonale nahrazuje. Je napsaný v jazyce Java a podporuje audio formáty WAV, AU, AIFF, MP3, OGG VORBIS a SPEEX. Je kompatibilní s WinAmp skins 2.0 a umožňuje podporu playlistů M3U a PLS. K projektu jsou zdrojové kódy, takže je možné si dopsat i další funkcionalitu:-) . Je na čase říct, že se jedná o jlGui a ke stažení je ze stránek javazoomu. English flag I belong to a small group of computer users that work with Mac OS X. I met with performance problems on this system while played music in integrated iTunes. I have resolved this problem by non standard way. I downloaded one opensource product which substitutes iTunes very well. It is written in Java language and supports audio formats WAV, AU, AIFF, MP3, OGG VORBIS and SPEEX. It is compatible with WinAmp skins 2.0 and allows support of M3U and PLS playlists. But you have sources so it is no problem to develop other functionality:-). It's time to say that it is jlGui and you can download it from pages of javazoom.
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