[GAME] Sudoku puzzle generator/game/solver

[nuukiaworld]

After a few days of hard working I succeeded to fit a sudoku generator based on Donald Knuth's DLX algorithm in my 6110. The freely available implementations of the algorithm were speed-optimized and required great amount of RAM during the solving process. Also, the only C implementation of DLX I found was very badly coded using only global variables and almost no comments, spaces(!) or any indents... :evil:

I programmed a sudoku game around the generator/solver engine, so you can play the puzzles with your phone. The generated puzzles can be also copied on paper and solved in traditional way, of course. There is also a custom grid editor, which allows entering third-party puzzles into the phone. – After that you can let the phone solve the puzzle in a few seconds.

http://www.panuworld.net/nuukiaworld/download/nokix/sudoku1.gif
Download Sudoku for DCT-3 1.13 here:
www.panuworld.net/nuukiaworld/download/nokix/ (http://www.panuworld.net/nuukiaworld/download/nokix/)

The game has been tested on 6110 only. If it fails on other phones, I guess that the reason is:
A) the sudoku engine allocates about 1,5 kB of RAM during generation/solving – if the allocation fails (not enough free heap memory), the phone hangs :-( <fixed, uses malloc_try() since version 1.10>
B) during the generation/solving process a built-in "progress bar" display message is displayed (see pictures on the download page) – if the script locates wrong DMI id for the message the user interface may behave incorrectly <fixed, uses NokiX-defined DMI_PROGRESS and DMI_PROGRESS_QUIT since version 1.10>
If the game works on your non-6110 phone and the "Generating sudoku" & "Finding solutions" progress bar messages are displayed correctly, please let others (and me) know!

[_Brutus]

I have a bad news :/ not work correctly in 5510 :/

[joci2000]

Great logical game.

Seems to work correctly on 3310 V6.39. The progress bar, solver and generator also works correctly.

Thx this game. :-D

[nuukiaworld]

I have a bad news :/ not work correctly in 5510 :/Thanks for this information. If you have problems with Sudoku on your phone, please report the problem in detail including how to reproduce it. I don't have any other phones than 6110 but by reading a detailed error report I can probably guess where the problem is and try to make the app more compatible.

If the final reason is the short of RAM during the generation process, then there is nothing that I can do. However, I can try to solve other problems by making an updated version for testing (so that I can find out the actual reason).

My personal target is to make my scripts as compatible as possible eventhough I'm working only with a 6110 — but also introduce new reversed features (e.g. built-in display messages with "progress bar" this time), which is always risky. :-D

@joci2000
I am really happy that Sudoku works on 3310 — the first versions of my scripts have usually failed on 3310s. :D

[_Brutus]

nuukiaworld - now I understand how to play that game :]

I have a QWERTY keyboard:
for example:

3 4 5
E R T
D F G

I'm press "r" and I must choose number with this keys (3,4,5,E,R,T,D,F,G)
where
key3 - 1
key4 - 2
key5 - 3
keyE - 4
keyR - 5
etc.

but before I'm pressed key1, key2, etc. ;]

In 5510 Sudoku always generating grid number 27979 :/
Progress bar speed are too slow ;]
Timer with seconds are to fast :/

Very sorry for my English, maybe You understand what I'm mean ;]

[nuukiaworld]

Thanks! Now I understand how the 5510 keys are mapped in NokiX, so I can modify the game so that a number can be entered using the number keys instead of 3 4 5 E R T D F G 0 on 5510. :-) But before that update I want to solve the other, more difficult things:
In 5510 Sudoku always generating grid number 27979
Progress bar speed are too slow
Timer with seconds are to fastAlways generating 27979, even when selecting "Random game"? Is the date and time set on your phone? If not, then set them and try again. (The random games are based on the phone's clock!)

Progress bar is very slow on all phones. This is because all available processing power has been directed to the sudoku engine. It is not an indication of a problem if the phone does not fail during the progress bar display.

Do you really mean that the min:sec game timer on the top-left corner of the display does not measure true seconds? :eek: It should, there are nothing special in that timer display. (Note, however, that the "Score" display below it may decrease faster than 1 point/sec.)

[druidbartek]

Thanks! Now I understand how the 5510 keys are mapped in NokiX, so I can modify the game so that a number can be entered using the number keys instead of 3 4 5 E R T D F G 0 on 5510. :-)
i saw in Your game that Ure using own_get_unify_keycode - it maps 2 key blocks in 5510, i think u know about it ;)
maybe try to use message.argv[0] instead of? it work properly on all dct3 and on 5510 also :-D

[nuukiaworld]

I didn't know about own_get_unify_keycode() details before yesterday because the SDK documentation and include file do not describe what that function exactly does. — Yesterday I looked at the assembly to see what it does on 5510. (The problem is that the documentation does not say what keys it maps "on the left and right side of the display". I didn't know that it uses also the numeric keys on the top row.)

I think that own_get_unify_keycode() interface is not the most flexible interface to unify these keyboards. In this game, the numeric keys are treated some times as arrows and some times as numbers. own_get_unify_keycode() should be replaced with generic own_get_keycode(), which has an argument that selects the mapping for 5510 (on other phones it just should return the argv[0]). The argument for own_get_keycode() could be then a combination of:

UKM_NONE (0) — returns plain argv[0] also on 5510
UKM_NPM5_CURSORS1 (1) — cannot be combined with CURSORS2
UKM_NPM5_CURSORS2 (2) — cannot be combined with CURSORS1
UKM_NPM5_LEFT (4) — maps the left side keys to number keys
UKM_NPM5_RIGHT (8) — maps the right side keys to number keys

I suggest Yak to evaluate this kind of change to the interface. Current way generates extra code in applications that some times need to map the 5510 and some times not. For example, currently I need to write:

key = ( app.state == STATE_ENTER_NUMBER ? message.argv[0] : own_get_unify_keycode(UKM_NONE) );

but the proposed way generates less code and looks more beautiful:

key = own_get_keycode( app.state == STATE_ENTER_NUMBER ? UKM_NONE : UKM_NPM5_LEFT | UKM_NPM5_RIGHT );

BTW. Can anyone explain why timers seem to run too quickly on 5510 (according to the compaint above)? Does NokiX have incorrect TICKS_PER_SECOND value for NPM-5?

[_Brutus]

Does NokiX have incorrect TICKS_PER_SECOND value for NPM-5?

No. Now when I playing everything is ok :/ I dont know what happened :/


Is the date and time set on your phone? If not, then set them and try again.

No, date and time wasn't set on my phone :/ after set everything is ok ;]


The random games are based on the phone's clock!

Why?

sorry for my english :/

[druidbartek]

The random games are based on the phone's clock!

Why?

sorry for my english :/
coz random games arent truly random - game using some kind of pseudorandom number generator rely on phones clock timestamp :razz:

[nuukiaworld]

No. Now when I playing everything is ok :/ I dont know what happened :/Fine. Now I know everything that need to be fixed. Let's see if I have time to publish a fixed version before Easter.
No, date and time wasn't set on my phone :/ after set everything is ok ;]Fortunately... :p -sigh- Yes, as druidbartek said, the pseudorandom generator rand() used in NokiX applications actually generate a known sequence of numbers. However, to improve this, before starting a random game, Sudoku initializes the random generator with current date/time value read from phone clock. — But if date/time is not set, the generator is initialized always with the same "clock is not set" value and the game 27979 appears. :(

[nuukiaworld]

New version 1.02 is now available (link in the first post). It contains two improvements:
Keyboard mapping is improved on 5510 (number keys are now used to enter numbers)
Same "random" game does not appear again and again if phone clock is not set.
Some background for the long time needed for sudoku generation: On level 3, the generated sudokus are completely random, unique-solution, and locally minimized (removing any clue number would result in multiple solutions). Before starting coding I though that it is not so difficult to generate sudokus. However, it really was: all my own algorithms used an infinite amount of time.

Luckily Professor Donald Knuth (http://en.wikipedia.org/wiki/Knuth) has formulated recursive, nondeterministic, depth-first, brute-force algorithm ("DLX" (http://en.wikipedia.org/wiki/Dancing_Links)) that can be used to speed up sudoku solving/generation. It is not very old, only a few years, which tells that the problem has been very difficult for computer scientists, too.

However, the public implementations of the DLX algorithm in C are speed-optimized and may need 50...100 kB of RAM during the solving process. — The solver engine in this DCT-3 Sudoku uses only 1,5 kB of RAM (which costs in the speed).

During the generation process on level 3, the puzzle must be completely solved 77 times. Solving an arbitary puzzle with my DLX implementation on DCT-3 takes up to one second. => Generating a sudoku takes something round one minute (depending on the phone). (Note that there should an option (e.g. "Quit") to interrupt the sudoku generation. Inform me if interrupting is not possible on your phone model.)

— If you have any problems with this game, please report. I'll try to fix them (only if I can find the reason)... :razz:

[_Brutus]

I'm not sure, but, when I press asterix key (during the game) on my screen are random pixels. In evening I put here screenshot. You understand? I'm hope ;]

[nuukiaworld]

when I press asterix key (during the game) on my screen are random pixels.Pressing * toggles the hints on and off. The hints are shown as groups of pixels in empty cells. The position of those pixels tell what numbers are allowed in that cell.

To understand the meaning of the pixels, you should compare their positions to the keyboard of a standard phone keyboard. A pixel in the top-left corner means that 1 is allowed, a pixel in the bottom-right corner means 9, etc...
*** 1,2,3,5,7,8 are allowed
*
**

*** all digits are allowed
***
***

* 1 and 9 are allowed

*In the easiest case, there is only one pixel visible in a cell and it tells the only number that can be entered in the cell.

BTW. There is a flaw in the game over handling which causes the continue option behave incorrectly if hangup key is pressed after completing the sudoku. I'll fix it some day.

[macg]

Hi:)
Sudoku is really great script, thanx, but I have some problems with it. I used this script for my 3310 with 6.39 firmware. It seem that wokrs correctly, but sometimes my phone hang for few seconds and than restart itself :???: .
If I remove sudoku, phone works right.
Does somebody know where should be the problem???

[LoMaster]

I have 3310 v6.39 and use the sudoku script with absolutely no problem. There is however a script that is known to cause random restarts - it's display_date.nrx by D:Virus. Maybe that's your problem...

One more possibility - you may have forgotten to do a full factory reset after flashing.

Hope that helps (and sorry if all this was obvious to you).

[macg]

Thank you for your replay, but I don´t use display_date.nrx by D:Virus and full factory reset i tried :cry: :???:

[joci2000]

Thank you for your replay, but I don´t use display_date.nrx by D:Virus and full factory reset i tried :cry: :???:


Where is this script in your project? try to move it up in your project to be processed earlier.

do you use hard modded firmware? or you just use the games?

[p_l_q]

on my 3310 v6.33 "genetaring" is just like neverending story:P

[macg]

Where is this script in your project? try to move it up in your project to be processed earlier.

do you use hard modded firmware? or you just use the games?

:)thanx for your advise,i´ll try it:)
I am not sure that I know what is hard modded firmware:( For modding I use only NokiX...

[sander18]

hi! i like your game really really much. i play it every day, it's my favourite one :D and i have some question about it.
could you modiffy your game for 96x65 screen. i used 3350 some time ago, and thought it would be nice if i could play it fullscreen.
btw. on 3350 the display_msg doesn't work (there is no "Grid saved" or solutions messages).

or if you could give it's project with soucre code then i could do this :D

PS. sorry for my english - i hope it isn't so bad...

[nuukiaworld]

It is finally time to release the updated version of DCT-3 Sudoku. The code has been partly rewritten and the most important new features are:

New level 1 added for beginners
Generated sudokus are now symmetric on levels 1, 2 (4-way) and 3 (2-way)
Pressing hangup when the game is over does not dismiss the game anymore
New scoring, starting from 6000 on all levels
Undo/redo functions added, replacing grid saving with #
Separate build for 96x65 displays, no flash space trade-off
Download link in the first message of this thread!

The undo/redo should improve the playability a lot because you can now do a guess and ar any time undo back to that moment to guess again. (Now it is easier than with the grid saving function.)

Note that the version for 96x65 displays have not been tested. It would be nice if anybody with such phone could post here a screen shot of the sudoku grid on large display. I'd like to check that it looks like I intended. :smile:

[druidbartek]

[...]Note that the version for 96x65 displays have not been tested. It would be nice if anybody with such phone could post here a screen shot of the sudoku grid on large display. I'd like to check that it looks like I intended. :smile:[...]

here you are :)

games menu:
http://druidbartek.info/pictures/sudoku/1.gif
intro bitmap - better than nothin' :P:
http://druidbartek.info/pictures/sudoku/2.gif
custom grid:
http://druidbartek.info/pictures/sudoku/3.gif
random game:
http://druidbartek.info/pictures/sudoku/4.gif

[chen2]

Sudoku puzzle is a very interesting game. Athough it is difficulty for me, I like it.:-D

[nuukiaworld]

@druidbartek
Thanks for the pictures. I succeeded to expand the game grid correctly so that it uses the whole display. :D However, I forgot the Intro picture completely. :oops:

There seem to be also a problem with the time display. The reason is probably that the fonts are larger in a 96x65 phone. - I did not know that. - The vertical positions of the texts must therefore be changed in the 96x65 version. I'll be back.

The new version 1.12 available now should fix the intro bitmap and time display problems on 96x65 displays. Game grid is also adjusted a little. The build for phones with 84x48 display should not have been changed.

[nuukiaworld]

Hello, this update has been laying in my phone and on my hard disk for nine months already but finally I had time to test and publish it.

Version 1.13 of Sudoku game prevents the problems which occur if you press the number/arrow keys during "Generating sudoku..." message. (Such keypresses resulted in corrupted sudoku puzzles in addition to visual crap during the generation.)

I have also another big update pending, that is RPN calculator 1.40. After release of that version, the RPN calculator will provide even more advanced support features for university-level physicists and even for artillery officers. :D