sudoku sequence generator

[zedd151]

I have this code where I create a list of valid sequences of 9 digits. Each sequence must only contain the digits 1-9, no zeroes.
Each digit must only occur once per sequence. There are 362880 valid sequences.
Example:
-------------
123456789 ; first valid sequence
123456798
123456879
...
...
987654321 ; last valid sequence
------------

This example writes the sequence as lines of ascii text. I did this to aid in visually inspecting the results. This algo works, but is painfully slow.
I am looking for ways to make this much faster. The result does not have to be ascii text. It could be binary data instead, or even dwords.

Code: [Select]


    include \masm32\include\masm32rt.inc
       
    .data


        number      dd 123456789 ; start with the first valid 'number'
       
        numstring   db 16 dup (0)
       
        hOutput     dd 0
        outfile     db "output.txt", 0
        crlf        db 0Dh, 0Ah, 0
        bw          dd 0
        num1        db 0
        num2        db 0
        num3        db 0
        num4        db 0
        num5        db 0
        num6        db 0
        num7        db 0
        num8        db 0
        num9        db 0
   
    .code
   
    start:


        invoke CreateFile, addr outfile, GENERIC_WRITE, FILE_SHARE_READ or FILE_SHARE_WRITE, 0, CREATE_ALWAYS, 0, 0
        mov hOutput, eax
      top:
        invoke dwtoa, number, addr numstring    ; generate decimal string from 'number'
       
        lea ecx, numstring                      ; test if "0" is present, skip writing string
        cmp byte ptr [ecx], "0"
        jz skipit
        cmp byte ptr [ecx+1], "0"
        jz skipit
        cmp byte ptr [ecx+2], "0"
        jz skipit
        cmp byte ptr [ecx+3], "0"
        jz skipit
        cmp byte ptr [ecx+4], "0"
        jz skipit
        cmp byte ptr [ecx+5], "0"
        jz skipit
        cmp byte ptr [ecx+6], "0"
        jz skipit
        cmp byte ptr [ecx+7], "0"
        jz skipit
        cmp byte ptr [ecx+8], "0"
        jz skipit
     
        mov num1, 0                             ; zero out individual digit counters
        mov num2, 0
        mov num3, 0
        mov num4, 0
        mov num5, 0
        mov num6, 0
        mov num7, 0
        mov num8, 0
        mov num9, 0
       
        mov edx, 0                              ; clear counter
      loop1:
      .if     byte ptr [ecx+edx] == "1"         ; increment for occurence of each 'digit'
        inc num1
      .elseif byte ptr [ecx+edx] == "2"
        inc num2
      .elseif byte ptr [ecx+edx] == "3"
        inc num3
      .elseif byte ptr [ecx+edx] == "4"
        inc num4
      .elseif byte ptr [ecx+edx] == "5"
        inc num5
      .elseif byte ptr [ecx+edx] == "6"
        inc num6
      .elseif byte ptr [ecx+edx] == "7"
        inc num7
      .elseif byte ptr [ecx+edx] == "8"
        inc num8
      .elseif byte ptr [ecx+edx] == "9"
        inc num9
      .endif
        inc edx                                 ; increment counter
        cmp edx, 9
        jnz loop1
       
        cmp num1, 1                             ; check if any digit appears more than once
        jnz skipit                              ; if so, skip writing string
        cmp num2, 1
        jnz skipit
        cmp num3, 1
        jnz skipit
        cmp num4, 1
        jnz skipit
        cmp num5, 1
        jnz skipit
        cmp num6, 1
        jnz skipit
        cmp num7, 1
        jnz skipit
        cmp num8, 1
        jnz skipit
        cmp num9, 1
        jnz skipit


        invoke WriteFile, hOutput, addr numstring, 9, addr bw, 0 ; write string
        invoke WriteFile, hOutput, addr crlf, 2, addr bw, 0      ; write CR/LF
      skipit:
        inc number
        cmp number, 987654321                   ; end after last valid 'number'
        jle top


        invoke CloseHandle, hOutput             ; close handle :P
        invoke ExitProcess, 0                   : exit :)


    end start
I am experimenting with ways of testing for valid sudoku grids. This will be a lookup table of sorts...
So, does anyone have any tips to make this much faster? I plan on using this code at runtime and not have to store a ~4MB listing in data.
Attachment removed, source code is above.

[NoCforMe]

OK, I'll bite. Took me all of 5 minutes to come up with this scheme:

Code: [Select]

[data]
Number DW ?
digit DB ?

[initialization for each 9-digit #]
MOV Number, 0

[get an ASCII digit, convert to binary]
SUB digit, '0'

[check a digit to see if it's already in number]
XOR CX, CX ;Clear entire 16-bit reg.

; "digit" is the binary digit to check:
MOV CL, digit ;Digit has been pre-checked, in range 1-9.
DEC CL ;Now in range 0-8
MOV AX, 1
SHL AX, CL ;Shift to bit 0-8 (1-9 in our system)
TEST Number, AX ;See if this bit is already set.
JNZ nogood
OR Number, AX ;It's OK, so set the bit for further checking.

Untested, but I'm pretty sure it'll work. See what I'm doing here?

[Bonus quiz: you don't even have to decrement CL to make the range 0-8; see why?]

[zedd151]

Untested, but I'm pretty sure it'll work. See what I'm doing here?

Not sure that this would be a fit for what I am trying to do unless I am missing something here. Would have to see it in the context of the code I posted, or a testbed of your choosing. The result does not have to be ascii (can convert later), The starting number is 123456789 decimal (not hex), we don't need anything lower since it would not meet the criteria (would contain zeroes), and the highest possible would be 987654321.
I'll play with it a little ...

[NoCforMe]

What I wrote will check any sequence of 9 digits for repeated digits. Try it.

You need to convert ASCII digits to binary (or generate them as binary in the first place). How to do that is in that code.

I'd write a testbed if I weren't frying other fish, but really, it's trivial. Walk the code through in your head; you'll see.

One thing: "Number" isn't a number, it's a bit field. You check your number one digit at a time.

[zedd151]

What I wrote will check any sequence of 9 digits for repeated digits. Try it.

I'll play with it a little ...    I like a good fish-fry

[NoCforMe]

OK, I'll do this much. Here's some code you can probably adapt pretty easily that'll check any set of 9 digits for duplicates. if you're using binary instead of ASCII, skip the SUB AL, '0' instruction. (You need to put the 9 digits in the NumberChars array. Or you can figure out some other scheme, like passing in a pointer. Shouldn't be hard.)

Code: [Select]

.data

NumberChars DB 9 DUP(?)
NumberBitfield DW ?

Digit DB ?

.code

; Assumes 9 ASCII digits have been put in NumberChars
; AND that they've been checked to be in the range '1'-'9'.
; Returns TRUE if # is OK (no repeated digits), FALSE otherwise.

CheckDigits PROC

PUSH ESI
MOV ESI, OFFSET NumberChars

MOV NumberBitField, 0 ;Clear bit field.
MOV EDX, 9 ;Loop counter.
numlp: LODSB ;Get next ASCII digit.
SUB AL, '0' ;ASCII--> binary.
MOV CL, AL ;Bit-shift count.
MOV AX, 1 ;Bit 0
SHL AX, CL ;Shift to bit 1-9
TEST NumberBitField, AX ;Is this "digit" already set?
JNZ nogood ;  Yep, so # is no good.
DEC EDX ;  Nope, so keep checking
JNZ numlp

good: MOV EAX, TRUE
JMP SHORT @F

nogood: XOR EAX, EAX ;EAX = FALSE
@@: POP ESI
RET

CheckDigits ENDP


[NoCforMe]

If you're generating sequences of binary #s and want to convert them to 9 ASCII digits, easy peasy:

Code: [Select]

; To get ASCII digits from a binary #:

DigitsFmt DB "%09u", 0

LOCAL buffer[32]:BYTE

INVOKE wsprintf, ADDR buffer, OFFSET DigitsFmt, <number>


[zedd151]

Here's some code you can probably adapt pretty easily that'll check any set of 9 digits for duplicates.

Okee, thanks. I'll test it first to see if it does what is expected of it. Tomorrow (its getting late) I will rewrite the code I have to put it into a procedure, to make timing comparisons between your code and my original code.   

I'll work on this tomorrow.

[zedd151]

After chewing on this idea for a while, it may be just be better, faster, and easier to simply store the full 4MB set of sequences in .data. I'll think about this more while I saw some logs tonite. ZZZzzz ...

[NoCforMe]

No, don't do that.

I went ahead and wrote a little console app that works. Try it out. It creates a file called "SudokuNums.dat". All numbers are valid Sudoku #s.

I set the upper limit at 333,333,333. It takes a little while but not too long.

Note to self: do not use wsprintf()! Waaaaay too slow. I generate the #s (ASCII) by hand here.

Code: [Select]

;============================================
; Sudoku valid number sequence generator
;
;============================================

.nolist
include \masm32\include\masm32rt.inc
.list


;============================================
; Defines, prototypes, etc.
;============================================


; How many numbers to CHECK (not generate):
$numberLimit EQU 333333333

WinMain PROTO

;============================================
; HERE BE DATA
;============================================
.data

NumberBitfield DW ?
NumberChars DB "000000000", 13, 10, 0
$numberLen EQU $ - NumberChars - 1 ;Less the terminating NULL.

OutputFilename DB "SudokuNums.dat", 0


;============================================
; CODE LIVES HERE
;============================================
.code


start: INVOKE WinMain
INVOKE ExitProcess, 0


;====================================================================
; Mainline proc
;====================================================================

WinMain PROC
LOCAL dummy:DWORD, fileHandle:HFILE, writeLen:DWORD, buffer[32]:BYTE

; Create an output file:
INVOKE CreateFile, OFFSET OutputFilename, GENERIC_WRITE, 0, NULL, CREATE_ALWAYS, 0, NULL
MOV fileHandle, EAX

; Generate a bunch of #s and check them for Sudoku-ness:
PUSH EBX
XOR EBX, EBX ;Number counter.

; Turn # into 9 ASCII digits:
nxtnum: MOV ECX, 9 ;Max. 9 digits
MOV EDX, OFFSET NumberChars + 8
nxtdgt: INC BYTE PTR [EDX]
CMP BYTE PTR [EDX], ':' ;Check for rollover.
JNE done ;  None, so we're done incrementing #.
MOV BYTE PTR [EDX], '0'
DEC EDX ;Next digit west.
LOOP nxtdgt

done: CALL CheckDigits ;Check for duplicate digits.
INC EBX ;Next #.
TEST EAX, EAX ;Did we get a good one?
JZ nogood ;  Nope.

; Write the good # to the output file:
INVOKE WriteFile, fileHandle, OFFSET NumberChars, $numberLen, ADDR dummy, NULL
nogood: CMP EBX, $numberLimit ;Are we done?
JB nxtnum ;  Nope, keep chuggin'.

exit99: POP EBX
INVOKE CloseHandle, fileHandle
RET



WinMain ENDP


CheckDigits PROC

; Assumes 9 ASCII digits have been put in NumberChars
; Returns TRUE if # is OK (no repeated digits), FALSE otherwise.
; Also throws out any #s with zeroes in them.


PUSH ESI
MOV ESI, OFFSET NumberChars

MOV NumberBitfield, 0 ;Clear bit field.
MOV EDX, 9 ;Loop counter.
numlp: LODSB ;Get next ASCII digit.
SUB AL, '0' ;ASCII--> binary.
JZ nogood ;No zeros allowed in this club!
MOV CL, AL ;Bit-shift count.
MOV AX, 1 ;Bit 0
SHL AX, CL ;Shift to bit 1-9
TEST NumberBitfield, AX ;Is this "digit" already set?
JNZ nogood ;  Yep, so # is no good.
OR NumberBitfield, AX ;  Nope, so set it.
DEC EDX ;  and keep checking
JNZ numlp

good: MOV EAX, TRUE
JMP SHORT @F

nogood: XOR EAX, EAX ;EAX = FALSE
@@: POP ESI
RET

CheckDigits ENDP


END start


[NoCforMe]

Go ahead and bump that upper limit up to 999,999,999. Takes less than a minute, writes a ~4 MB file. (Too lazy to post revised app.)

[zedd151]

I set the upper limit at 333,333,333. It takes a little while but not too long.

 
I was just about to turn off the computer but checked recent posts...
I changed the upper limit to 987654321. It looks quite a bit faster than what I had originally. Now I will change the starting point to 123456788 ...

Code: [Select]

;============================================
; Sudoku valid number sequence generator
;
;============================================

.nolist
   include \masm32\include\masm32rt.inc
.list


;============================================
; Defines, prototypes, etc.
;============================================


; How many numbers to CHECK (not generate):
$numberLimit      EQU 987654321


WinMain      PROTO


;============================================
; HERE BE DATA
;============================================
.data


NumberBitfield      DW ?
NumberChars      DB "123456788", 13, 10, 0
$numberLen      EQU $ - NumberChars - 1      ;Less the terminating NULL.


OutputFilename   DB "SudokuNums.dat", 0


;============================================
; CODE LIVES HERE
;============================================
.code


start:   INVOKE   WinMain
   INVOKE   ExitProcess, 0


;====================================================================
; Mainline proc
;====================================================================


WinMain   PROC
   LOCAL   dummy:DWORD, fileHandle:HFILE, writeLen:DWORD, buffer[32]:BYTE


; Create an output file:
   INVOKE   CreateFile, OFFSET OutputFilename, GENERIC_WRITE, 0, NULL, CREATE_ALWAYS, 0, NULL
   MOV   fileHandle, EAX


; Generate a bunch of #s and check them for Sudoku-ness:
   PUSH   EBX
   XOR   EBX, EBX      ;Number counter.


; Turn # into 9 ASCII digits:
nxtnum:   MOV   ECX, 9         ;Max. 9 digits
   MOV   EDX, OFFSET NumberChars + 8
nxtdgt:   INC   BYTE PTR [EDX]
   CMP   BYTE PTR [EDX], ':'   ;Check for rollover.
   JNE   done         ;  None, so we're done incrementing #.
   MOV   BYTE PTR [EDX], '0'
   DEC   EDX         ;Next digit west.
   LOOP   nxtdgt


done:   CALL   CheckDigits      ;Check for duplicate digits.
   INC   EBX         ;Next #.
   TEST   EAX, EAX      ;Did we get a good one?
   JZ   nogood         ;  Nope.


; Write the good # to the output file:
   INVOKE   WriteFile, fileHandle, OFFSET NumberChars, $numberLen, ADDR dummy, NULL
nogood:   CMP   EBX, $numberLimit   ;Are we done?
   JB   nxtnum         ;  Nope, keep chuggin'.


exit99:   POP   EBX
   INVOKE   CloseHandle, fileHandle
   RET


WinMain      ENDP


CheckDigits   PROC


; Assumes 9 ASCII digits have been put in NumberChars
; Returns TRUE if # is OK (no repeated digits), FALSE otherwise.
; Also throws out any #s with zeroes in them.


   PUSH   ESI
   MOV   ESI, OFFSET NumberChars


   MOV   NumberBitfield, 0   ;Clear bit field.
   MOV   EDX, 9         ;Loop counter.
numlp:   LODSB            ;Get next ASCII digit.
   SUB   AL, '0'         ;ASCII--> binary.
   JZ   nogood         ;No zeros allowed in this club!
   MOV   CL, AL         ;Bit-shift count.
   MOV   AX, 1         ;Bit 0
   SHL   AX, CL         ;Shift to bit 1-9
   TEST   NumberBitfield, AX   ;Is this "digit" already set?
   JNZ   nogood         ;  Yep, so # is no good.
   OR   NumberBitfield, AX   ;  Nope, so set it.
   DEC   EDX         ;  and keep checking
   JNZ   numlp


good:   MOV   EAX, TRUE
   JMP   SHORT @F


nogood:   XOR   EAX, EAX      ;EAX = FALSE
@@:   POP   ESI
   RET


CheckDigits   ENDP


   END   start
later:
Yes indeed much faster.    My original code took eons in comparison.

[NoCforMe]

You need to also set EBX to the initial start # (probly wasn't clear that you needed to do that); as it is it starts from 0 (XOR EBX, EBX).

[zedd151]

You need to also set EBX to the initial start # (probly wasn't clear that you needed to do that); as it is it starts from 0 (XOR EBX, EBX).

   I'll look at it today in olly and follow EBX. It performed so much better than my original code, that I did not do due diligence. It did produce the correct results btw. I'll fiddle with it. Maybe it is processing after 987654321?


It is well known that there are only 362880 valid values for the entire sequence from 123456789-987654321 (all valid). So, if we only increment what is written to file then we could use 362880 as the count (EBX) to stop processing at. I am on the porch at the moment but will look into this further when I'm at my computer.

Fun Fact:

There are 6,670,903,752,021,072,936,960 possible solvable Sudoku grids that yield a unique result (that's 6 sextillion, 670 quintillion, 903 quadrillion, 752 trillion, 21 billion, 72 million, 936 thousand, 960 in case you were wondering).

credit: https://www.britannica.com  (and others as well)    In any case way too many for the memory + all my hard drive space. (All memory cards I own + all hard drives I own)   So I don't think I will be storing that database any time soon. 

[zedd151]

Final modifications to the code

Code: [Select]

.nolist
   include \masm32\include\masm32rt.inc
.list


;============================================
; Defines, prototypes, etc.
;============================================


; How many numbers to CHECK (not generate):
$numberLimit      EQU 987654321  ; zedd151 modification


WinMain      PROTO


;============================================
; HERE BE DATA
;============================================
.data


NumberBitfield      DW ?
NumberChars      DB "123456788", 13, 10, 0  ; zedd151 modification
$numberLen      EQU $ - NumberChars - 1      ;Less the terminating NULL.


OutputFilename   DB "SudokuNums.dat", 0


;============================================
; CODE LIVES HERE
;============================================
.code


start:   INVOKE   WinMain
   INVOKE   ExitProcess, 0


;====================================================================
; Mainline proc
;====================================================================


WinMain   PROC
   LOCAL   dummy:DWORD, fileHandle:HFILE, writeLen:DWORD, buffer[32]:BYTE


; Create an output file:
   INVOKE   CreateFile, OFFSET OutputFilename, GENERIC_WRITE, 0, NULL, CREATE_ALWAYS, 0, NULL
   MOV   fileHandle, EAX


; Generate a bunch of #s and check them for Sudoku-ness:
   PUSH   EBX
   XOR   EBX, EBX      ;Number counter.


; Turn # into 9 ASCII digits:
nxtnum:   MOV   ECX, 9         ;Max. 9 digits
   MOV   EDX, OFFSET NumberChars + 8
nxtdgt:   INC   BYTE PTR [EDX]
   CMP   BYTE PTR [EDX], ':'   ;Check for rollover.
   JNE   done         ;  None, so we're done incrementing #.
   MOV   BYTE PTR [EDX], '0'
   DEC   EDX         ;Next digit west.
   LOOP   nxtdgt


done:   CALL   CheckDigits      ;Check for duplicate digits.
   TEST   EAX, EAX      ;Did we get a good one?
   JZ   nogood         ;  Nope.


; Write the good # to the output file:
   INVOKE   WriteFile, fileHandle, OFFSET NumberChars, $numberLen, ADDR dummy, NULL
   INC   EBX         ;Next #. ;; moved 'inc ebx' here to counted only what is written ; zedd151 modification
nogood:   CMP   EBX, 362880 ; compare with known number of valid sequences  ; zedd151 modification
   JB   nxtnum         ;  Nope, keep chuggin'.
exit99:   POP   EBX
   INVOKE   CloseHandle, fileHandle
   RET


WinMain      ENDP


CheckDigits   PROC


; Assumes 9 ASCII digits have been put in NumberChars
; Returns TRUE if # is OK (no repeated digits), FALSE otherwise.
; Also throws out any #s with zeroes in them.


   PUSH   ESI
   MOV   ESI, OFFSET NumberChars


   MOV   NumberBitfield, 0   ;Clear bit field.
   MOV   EDX, 9         ;Loop counter.
numlp:   LODSB            ;Get next ASCII digit.
   SUB   AL, '0'         ;ASCII--> binary.
   JZ   nogood         ;No zeros allowed in this club!
   MOV   CL, AL         ;Bit-shift count.
   MOV   AX, 1         ;Bit 0
   SHL   AX, CL         ;Shift to bit 1-9
   TEST   NumberBitfield, AX   ;Is this "digit" already set?
   JNZ   nogood         ;  Yep, so # is no good.
   OR   NumberBitfield, AX   ;  Nope, so set it.
   DEC   EDX         ;  and keep checking
   JNZ   numlp


good:   MOV   EAX, TRUE
   JMP   SHORT @F


nogood:   XOR   EAX, EAX      ;EAX = FALSE
@@:   POP   ESI
   RET


CheckDigits   ENDP


   END   start


Now does not start at zero (but 123456788) and does not go past 987654321   


It took only 12 Mississippi's to finish. (One Mississipi, two Mississippi, ... etc.)    Original too many to count.     
At any rate this is fast enough for now. Many thanks, NoCforMe for your contribution.    I may reinvestigate this at some point in the future to make the rest of the code quicker. Maybe unrolling the outer loop? or inner loop?
At any rate, I dabble with sudoku related code only occasionally, and usually working on other projects concurrently with the more experimental sudoku related code. So, it may be a while before I get back to this again.