Simple Sudoku Solver

Usage Show & Tell
1 
; simple sudoku solver based on the Python example from computerphile:
; https://www.youtube.com/watch?v=G_UYXzGuqvM&list=WL&index=228

grid: [
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
]

print-grid: func [<with> grid <local> output][
    output: copy ""
    count-up i 81 [
        append output grid/:i
        either i mod 9 = 0 [
            append output newline
            if all [ i mod 27 = 0
                     i < 81        ][
                append output "------+-------+------^/"
            ]
        ][
             append output either any [ i mod 9 = 3
                                        i mod 9 = 6 ][ " | " ][ " " ]
        ]
    ]
    print output
]

possible: func [
    y
    x
    n
    <with> grid
    <local> x0 y0
][
    count-up i 9 [
        if n = grid/(9 * (y - 1) + i) [
            return false
        ]
    ]
    count-up i 9 [
        if n = grid/(9 * (i - 1) + x) [
            return false
        ]    
    ]
    x0: ((to integer! (x - 1) / 3)) * 3 + 1
    y0: ((to integer! (y - 1) / 3)) * 3 + 1
    count-up i 3 [
        count-up j 3 [
            if n = grid/(9 * (y0 + (i - 1) - 1) + (x0 + (j - 1))) [
                return false
            ]
        ]
    ]
    return true
]

solve: func [<with> grid][
    count-up y 9 [
        count-up x 9 [
            if 0 = grid/(9 * (y - 1) + x) [
                count-up n 9 [
                    if possible y x n [
                        grid/(9 * (y - 1) + x): n
                        solve
                        grid/(9 * (y - 1) + x): 0 ; backtracking
                    ]
                ] return _
            ]
        ]
    ]
    print-grid
]

The result of running it:

>> solve
5 3 4 | 6 7 8 | 9 1 2
6 7 2 | 1 9 5 | 3 4 8
1 9 8 | 3 4 2 | 5 6 7
------+-------+------
8 5 9 | 7 6 1 | 4 2 3
4 2 6 | 8 5 3 | 7 9 1
7 1 3 | 9 2 4 | 8 5 6
------+-------+------
9 6 1 | 5 3 7 | 2 8 4
2 8 7 | 4 1 9 | 6 3 5
3 4 5 | 2 8 6 | 1 7 9

== _
2

I've also adapted this example to make it a test.

It needed to update the PATH!s to TUPLE!s, because Ren-C uses tuples to pick fields out of objects.

 append output grid/:i

I deprecated this syntax, because I didn't believe that GET-WORD!s belonged in PATH! or TUPLE! slots.

So you'd instead write:

 append output grid.(i)

The rationale behind not having GET-WORD!s in tuple slots (besides that I think it looks ugly) is that if you could put a GET-WORD! in the first slot, you wouldn't know what this is:

:grid.1

Is that a GET-PATH! with a WORD! in the first slot? Or is it a plain PATH! with a GET-WORD! in the first slot? Similar arguments for why you don't want SET-WORD!s apply for the tail.

Overall I feel this prohibition has held up as a good rule.

2 Likes