include 'format/format.inc'
FORMAT PE64 CONSOLE 6.0 at $10000 on "NUL"
        SECTION '.flat' CODE READABLE WRITEABLE EXECUTABLE
        POSTPONE
                msvcrt_name db 'msvcrt',0
                _exit db 0,0,'exit',0
                __printf_p db 0,0,'_printf_p',0
                align 8
                DATA IMPORT
                        dd 0,0,0,RVA msvcrt_name,RVA msvcrt_table
                        dd 0,0,0,0,0
                        align 8
                        msvcrt_table:
                                exit dq RVA _exit
                                _printf_p dq RVA __printf_p
                                dq 0
                END DATA
        END POSTPONE
;###############################################################################



Puzzle000 db \
5,3,0,0,7,0,0,0,0,\
6,0,0,1,9,5,0,0,0,\
0,9,8,0,0,0,0,6,0,\
8,0,0,0,6,0,0,0,3,\
4,0,0,8,0,3,0,0,1,\
7,0,0,0,2,0,0,0,6,\
0,6,0,0,0,0,2,8,0,\
0,0,0,4,1,9,0,0,5,\
0,0,0,0,8,0,0,7,9

; Each location has a linearized form [0,80]. Additionally, a location belongs
; to three groups: row, column, square. The values here convert the linearized
; index into the member groups.
align 64 ; cache friendly
TriQuantize:
repeat 9, j:0
        repeat 9, i:0
                db -i ; delta to current row start
                db -j*9 ; delta to current column start
                ; delta to current square start
                db -((i mod 3) + 9*(j mod 3))
        end repeat
end repeat


_format db "Looking for solutions for:",13,10
_floormat db "%c %c %c %c %c %c %c %c %c",13,10,0

Sudoku__PrettyPrint:    ; nothing fancy, just replace zero with period
        push rsi
        mov rsi,rbp
        push rdi
        push rbp
        mov rbp,rsp
        sub rsp,10*8
        and rsp,-16

        mov edi,9
.LLL:   mov edx,1
        xor eax,eax
.LL:    mov qword[rsp+rdx*8],'0'
        lodsb
        test al,al
        jnz .num
        add qword[rsp+rdx*8],'.' - '0'
.num:   add qword[rsp+rdx*8],rax
        add edx,1
        cmp edx,10
        jc .LL

        mov rdx,[rsp+8]
        mov r8,[rsp+16]
        mov r9,[rsp+24]
        call [_printf_p]
        lea rcx,[_floormat]

        sub edi,1
        jnz .LLL

        mov rsp,rbp
        pop rbp
        pop rdi
        pop rsi
        retn


; RBP : global puzzle pointer
; RDI : pointer of current trial + 1
align 64 ; cache friendly
Validate_XYN:
        ; RSI : linearized index of current trial
        neg rbp
        lea rsi,[rbp+rdi-1]
        neg rbp

        ; check current row
        movsx rdx,byte[TriQuantize+rsi*2+rsi]
        repeat 9, i:0
                cmp [(rdi-1)+rdx+i],cl
                jz .false
        end repeat

        ; check current column
        movsx rdx,byte[TriQuantize+rsi*2+rsi+1]
        repeat 9, i:0
                cmp [(rdi-1)+rdx+9*i],cl
                jz .false
        end repeat

        ; check current square
        movsx rdx,byte[TriQuantize+rsi*2+rsi+2]
        repeat 3, j:0
        repeat 3, i:0
                cmp [(rdi-1)+rdx+9*j+i],cl
                jz .false
        end repeat
        end repeat
.false: retn


; Sudoku solver :
TryStart:
        mov rdi,rbp ; from start
.Try:   push rdi
        mov al,0
        neg rdi
        lea rcx,[81+rdi+rbp]
        neg rdi
        repnz scasb
        jnz .end                        ; no zeroes to fix
                mov ecx,9
        .A:     call Validate_XYN
                jz .B
                mov [rdi-1],cl          ; attempt
                call .Try               ; recurse
                movzx ecx,byte [rdi-1]  ; restore counter
                mov byte[rdi-1],0       ; clear attempt
        .B:     loop .A
        pop rdi
        retn

.end:   pop rdi
        lea rcx,[_floormat-1]
        call Sudoku__PrettyPrint
        retn
;###############################################################################
        ENTRY $
        pop rax ; this doesn't return
        lea rbp,[Puzzle000]
        lea rcx,[_format]
        call Sudoku__PrettyPrint
        call TryStart
        call [exit]
        int3    

;===============================================;
;           ****  Hugi Compo 25  ****           ;
;            Sudoku Solver - 62 bytes           ;
;-----------------------------------------------;
;         G3 / tgm80 (at) mail (dot) ru         ;
;       TFx / tfx (at) bitmaster (dot) it       ;
;     Digimind / digimind (at) aha (dot) ru     ;
;===============================================;

use16
org 100h

        mov     ah, 3fh         ;ah = 3f -> input
        mov     dx, bp          ;bp = buffer
InOutExit:      
        int     21h                     ;input/output/exit
        xchg    ax, cx          ;cx = length
        inc     bx                      ;stdout handle
Solve:
        mov     [bp+si], al             ;digit is ok            
Empty:
        dec     si                      ;find empty cell
        js      InOutExit               ;if not found output solution, then exit
        mov     ax,4031h                ;ah = 40 -> output/inc ax
ChkDgt:
        cmp     byte [bp+si], '.'       ;is empty?
        jne     Empty                   ;if empty check it else continue
        mov     di, cx
Next:
        dec     di                      ;find digit
        pusha
        js      Solve                   ;if no more digits set and recurse
        cmp     [bp+di], al             ;else search
        jne     SetOF
        xchg    ax, di          ;get digit position
Split:
        aam     19                      ;split row and column
        imul    ax, 11          ;find 3x3 group
        xchg    ax, si          ;get empty cell position
        inc     bx
        jpo     Split                   ;split empty cell position
        xor     ax, si          ;compare cell positions
        test    ax, 0e0c0h              ;same 3x3 group?
        jle     NOk
SetOF:
        mul     ah                      ;same column or same row?       
NOk:
        popa
        jo      Next                    ;next position
        mov     byte [bp+si], '.'       ;empty cell     
        cmp     al, 39h                 ;no more digits?        
        je      NOk
        jmp     ChkDgt-1
    

;Sudoku Puzzle Solver for Hugi Compo 25
;Coded by G3 (tgm80@mail.ru)
;Compile: fasm.exe entry.asm entry.com
;Usage: entry.com <filename.puz

;The input consists of nine lines. Each line contains only the ASCII
;characters 1 through 9, "." and space; and is terminated with a carriage
;return and line feed (in that order). The "." indicates an empty cell.
;One space character separates each printable character.

;For example, the above puzzle would have this input:
;4 3 . . . . . 8 .<cr><lf>
;9 7 8 . . . . 6 5<cr><lf>
;. . . 8 6 9 . . 3<cr><lf>
;. . 5 . . 4 6 . .<cr><lf>
;. . 1 9 5 8 3 . .<cr><lf>
;. . 3 2 . . 9 . .<cr><lf>
;5 . . 1 7 3 . . .<cr><lf>
;8 6 . . . . 5 3 1<cr><lf>
;. 1 . . . . . 4 2<cr><lf>

        org     100h            ;assume bx=0, ch=0, si=100h
        mov     ah,3Fh          ;ah=3Fh - read
        mov     dx,2EFFh        ;dh='.', dl=-1
        mov     bp,dx           ;bp=dx - offset of puzzle array 
L10:
        mov     cl,171          ;number of bytes to read/write
        int     21h             ;read/write/exit
        inc     bx              ;bx=1 - handle to stdout
L20:    
        mov     [si+bp],al      ;make trial entry with digit
        pusha                   ;save digit and index of cell
L30:
        dec     si              ;next cell
        js      L10             ;jump if puzzle solved
        cmp     [si+bp],dh      ;[si+2EFF]='.' ?
        jnz     L30             ;loop while cell is not empty
        mov     ax,4031h        ;ah=40h - write, al='1' / 40h - inc ax
L40:
        cmp     al,3Ah
        jz      L70             ;jump if al>'9'
        mov     cl,171          ;size of puzzle array
        mov     di,dx           ;di=dx - offset of puzzle array 
L50:                            ;search for cell contains the digit in al with
        repnz   scasb           ;identical row or column or 3x3 region coordinates
        jnz     L20             ;jump if digit in al is not already used
        pusha                   ;save digit and index of cell
        xchg    ax,si           ;al=si&00FF - index of first cell
L60:
        aam     19              ;ah=al/19 - row, al=al%19 - column
        imul    bp,ax,11        ;ah/3=(ah*11)>>5, al/6=(al*11)>>6
        or      bp,9F3Fh        ;bp=1rr11111cc111111 where rr=row/3, cc=column/6
        xor     bx,bp           ;compare 3x3 region coordinates of two cells
        xchg    ax,di           ;al=di&00FF - index of second cell
        js      L60             ;loop 2 times
        xor     ax,di           ;compare row and column of two cells
        mul     ah              ;set al=0 if al=0 or ah=0
        cmp     al,1            ;set cf=1 if al=0 (rows or columns are equal)
        dec     bx              ;set zf=1 if bx=1 (3x3 region coordinates are equal)
L70:    
        popa                    ;restore digit and index of cell
        jnbe    L50             ;jump if cf=0 and zf=0 
        mov     [si+bp],dh      ;undo trial entry
        jmp     L40-1           ;next digit

;P.S. Best regards to all competitors and organizers and my girlfriend Nadya!    

If we watch an expert player, it seems clear to me that Knuth's Dancing Links algorithm closely mimics the grouping and (bulk) exclusion of possibilities.

;the permutations that leave sudoku unchanged are:
;       (a) rotate the grid 90 degrees
;       (b) swap the top two rows
;       (c) swap the top two bands
;       (d) swap any two cell values for all cells with those values    

So where is the crossover point where brute force becomes slower than more advanced methods?

I think there could be some kind of mega=sudoku. The normal 9x9 is too easy for a computer. Even with the most naive trial and backtrack brute-forcing algorithm it is less than a millisecond and it is done.