Simple Games - Research and Development

[zedd151]

Okay. Currently having a little difficulty with ....
But here is a version with a game pre-loaded for anyones amusement. Not checking for validity of moves, so it is possible to put a number into a cell that doesn't belong there. Working on the code for invalid moves at the moment. Will have to continue that later though... busy... busy...


The game has a rating of 1013. Not very difficult but not very easy either. 
For anyone interested, I used a program called "Hodoku.exe" to generate that sudoku in the attached example.

[zedd151]

Much more coming in the next few days.    I had a major breakthrough and will be working on that new code to make it ready for posting... 


It may not take as long as I thought to finish this...          ...well maybe?
edit to add:

The new code I have decided to break out into a separate test piece. I found a minor but noticeable flaw that was hard to track down while in the GUI full game version. Now will be better able to debug this code to make it perform as it should...


Edit =    Houston we have a problem. Debugging or rather bug hunting time...

[zedd151]

As part of my research, I found a sudoku solver that uses backtracking. Meaning it uses a sort of optimized brute force method of solving. It places a digit in numerical order; if the rest of the puzzle not solved with that digit, the solver goes back to where it first placed that digit and tries the next digit in sequence, and so on. All the way to a solved puzzle. If a puzzle has a unique solution the solver will find it. If more than one solution, the solver will find ONE solution and exit.

Speaking of sudoku solvers...
I found online a solver that used NASM code which I had already converted.

For anyone interested here is the code that I had converted to MASM syntax for the solver    ; it's in the attached zip file.
The url to the original sources is in the .asm file.


Damn, I edited the original post that was here when I meant only to quote it.
Anyway the gist of that post explained that I will use the attached solver as a method to check whether a given sudoku puzzle is valid and solvable. The caveats are that even a puzzle that is completely empty is considered valid, as it does'nt expressly violate sudoku rules. Also the solver cannot detect if there is a unique solution. But this is a starting point anyway. I will try to modify the solver so it tries different branches to determine if more than one valid solution can be found. That would be a fair test for uniqueness.. but that would have to come later.... Will also add checking if the puzzle grid is empty or not.
edit =Reattached solver.zip.

[zedd151]

Almost finished completing the GUI code. Have this version stripped of everything except for the GUI code, and cell highlighting. Will post it as soon as it is complete (GUI for sudoku - display and GUI example only, no sudoku board processing). Once I do a thorough testing and debugging of this code, will add the sudoku related code to it. I gotta go; have to walk the dog. When I return will get back to coding... 

[FORTRANS]

Hi,

Damn, I edited the original post that was here when I meant only to quote it.
Anyway the gist of that post explained that I will use the attached solver as a method to check whether a given sudoku puzzle is valid and solvable. The caveats are that even a puzzle that is completely empty is considered valid, as it does'nt expressly violate sudoku rules. Also the solver cannot detect if there is a unique solution. But this is a starting point anyway. I will try to modify the solver so it tries different branches to determine if more than one valid solution can be found. That would be a fair test for uniqueness.. but that would have to come later.... Will also add checking if the puzzle grid is empty or not.

   The solver I mentioned in reply #61 does work correctly.  An
executable (for DOS?) was posted as a BATch file.  And a X86
source was also posted, though in his own assembler syntax.
The OS specific calls were separated out to ease a translation.
I found it useful as a starting point for my Sudoku generator.
Though that ended up as a FORTRAN program.

Cheers,

Steve N.

[zedd151]

The solver I mentioned in reply #61 does work correctly.

I had some trouble navigating/finding what looking for there @alt.lang.asm . I found some things, but not sure what you had intended. I wound up in a German language thread somehow. Anyway, I had started scouring other leads that day and found some promising material. If you have a direct link to what you are referring to in post #61 might be easier for me... (or have something to attach) I would like to see it.
In any case appreciate your help.  I could go and take another look later though, too.

[FORTRANS]

Hi,

If you have a direct link to what you are referring to in post #61 might be easier for me... (or have something to attach) I would like to see it.

   Hopefully this link will help:

https://groups.google.com/g/alt.lang.asm/c/CpmhKtqWIH4
Started  "Nov 29 2007"

   Search on Herbert Kleebauer:
At least:  Dec 1, 2007   Dec 4, 2007, 1:42:27 AM      Dec 4, 2007, 2:16:17 AM

   It is rather a long, mixed up, and wordy set of postings.  It
was a while back, but at the time I put some effort into it.  I
translated his code into 16-bit MASM code.  Just to understand
it.  I think the work might be on a computer that is having some
problems with a UPS.  So a bit slow to get at my old work just
now.  I just transferred the end product to this computer to work
on the FORTRAN code.

HTH,

Steve N.

[zedd151]

Ah, FORTRANS I probably had found what you had intended. At the time I didn't realize I was SUPPOSED to be looking for DOS code, and in a batch file nonetheless. I should have copied what I found then, I will go and look for that again, once I'm back at the house. I'm out and about at the moment. Posting this from my iPad

[zedd151]

Side note: most probably I wouldn't want to see the FORTRAN version. 

[FORTRANS]

Side note: most probably I wouldn't want to see the FORTRAN version. 

   I can probably guarantee that.  I am not sure I want to look at it now.

[zedd151]

Steve, does this look like part of the code I am supposed to look at?

Main: fninit
call 'comctl32.InitCommonControls'
call 'user32.CreateAcceleratorTableA' accelerators,
ACCELS
mov d$hAccel eax
call 'kernel32.GetModuleHandleA' &NULL
cmp eax 1 | jc ExitProg | mov d$wcx@hInstance eax
call 'user32.LoadIconA' &NULL &IDI_APPLICATION
cmp eax 1 | jc ExitProg | mov d$wcx@hIcon eax
call 'user32.LoadCursorA' &NULL &IDC_ARROW
cmp eax 1 | jc ExitProg | mov d$wcx@hCursor eax
call 'user32.LoadMenuA', d$wcx@hInstance, M00_Menu
mov d$hMenu,eax
; Register the window class for the main window.
call 'user32.RegisterClassExA' wcx
cmp eax 1 | jc ExitProg
call 'user32.AdjustWindowRectEx' rect,
&WS_OVERLAPPED+&WS_CAPTION+&WS_SYSMENU+&WS_MINIMIZEBOX,
&TRUE &NULL
cmp eax 1 | jc ExitProg

Looks like it will need to be deciphered/translated if thats the case. May take a little while.

[FORTRANS]

Hi,

Steve, does this look like part of the code I am supposed to look at?

Main: fninit
call 'comctl32.InitCommonControls'
<snip>

  No, it starts off with this.

Code: [Select]

:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

The source code:

        @=$100
        bclr.w  #10,sr

;***********************************************************************
; read 81 digits from stdin, anything else is ignored, 0 for unknown
;***********************************************************************

        move.l  #brett,r5
        move.l  #81,r2
   _10: bsr.l   getc
        sub.b   #'0',r0
        blo.b   _10
        beq.b   _20
        cmp.b   #9,r0
        bhi.b   _10
        eor.l   r1,r1
        bset.l  r0,r1
        move.l  r1,(r5)
        br.b    _30
   _20: move.l  #$03fe0000,(r5)

   The code is X86 made to look like Motorola 68000 code (or some-
thing similar).  I also used a disassembler on the sudo.com file.  With
both listings (the one supplied and one from the disassembly) a mix
and match created a MASM compatible program to recreate the
sudo.com.  From there I modified the code to run on an older 80186
computer.  And all that got me to understand the logic of his program.

   The executable is posted a few times as BATch files.

Code: [Select]

:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
@echo off
echo Bj@jzh`0X-`/PPPPPPa(DE(DM(DO(Dh(Ls(Lu(LX(LeZRR]EEEUYRX2Dx=>sudo.com
echo 0DxFP,0Xx.t0P,=XtGsB4o@$?PIyU WwX0GwUY Wv;ovBX2Gv0ExGIuht6>>sudo.com
echo }e{f?D[@xe?c??P@ge?s?Bu?ok??suq\H{P?eov\eQp[AjNwHefdGjUKFe>>sudo.com


Code: [Select]

:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
@echo off
echo hD1X-s0P_kUHP0UxGWX4ax1y1ieimnfeinklddmemkjanmndnadmndnpbbn>sudo.com
echo hhpbbnpljhoxolnhaigidpllnbkdnhlkfhlflefblffahfUebdfahhfkokh>>sudo.com
echo wPajQJ///MKiF0///M5uqA///k1AmNDRFkH1r0jNl7hNDgekbNKWKgC1bNq>>sudo.com

   They create "sudo.com"  the solver as explained in the postings.

Cheers,

Steve N.

[zedd151]

Ah, ok. I copied that full page to HTML file. I'll look into it later this evening. Thanks again.


some time later...

lmao.    A com file. Took me a hot minute to realize that the com file runs right after it is created. I'm surprised it still runs under Windows 7, thought I'd have to scrounge a copy of Windows 98/95? lol. Surely it would'nt run under Windows 10 though. I have never had any experience with com files, except the occasion use of the old COMMAND.COM.

It does indeed work (sudo.com). But have no clue how I'd incorporate this into my project. It will be handy for making valid sudoku puzzles though. Ill play with this, making some puzzles...

[zedd151]

> FORTRANS sudo.com works very well so far. I've been testing it for a while. For some extremely difficult puzzles it fails to find a solution in one recursion though. This puzzle has been tested and is valid with a unique solution.
example:

97.18..3.
..3.6...2
.......9.
5..2..6..
.3.7.4.2.
..7..6..1
.6.......
3...4.2..
.8..91.67


not solveable with one recursion

In the brute force solver, I put a counter in it. Turns out that the brute force solver uses 942,879,776 recursions for the same puzzle. 
In all fairness, that puzzle has a difficulty rating of 7782 as rated by "Hodoku" the program that generated it. Most 'Hard' puzzles are in the 1000-2000 range, and sudo.com solves those quite handily. On the other hand there is a puzzle in the 13000 range and sudo.com solved it without issues. As stated though, for the majority of puzzles it does quite well.

So I would say that sudo.com still is very useful tool and does a very good job; but it does have its limitations.

[FORTRANS]

Hi,

So I would say that sudo.com still is very useful tool and does a very good job; but it does have its limitations.

   Well, very good that you found it useful.  Of course it would
have limitations.  If the thread was not so old, Herbert wanted
to see a puzzle that wasn't solved with one recursion.  And for
my uses it worked, so I pointed it out to you.

   Just for sillyness, how do sudo.com and the brute force solver
compare in size and speed?  I liked that sudo.com was small
enough that I could follow its logic.  And it seemed quick to me
as well.

Cheers,

Steve N.