1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
function solveSudoku(board: string[][]): void {    const spaces: number[] = [];    const rows = new Array(9).fill(0).map(() => number_char_set(false));    const columns = new Array(9).fill(0).map(() => number_char_set(false));    const subboxes = new Array(3)        .fill(0)        .map(() => new Array(3).fill(0).map(() => number_char_set(false)));    for (let i = 0; i < 9; i++) {        for (let j = 0; j < 9; j++) {            const char = board[i][j];            if (char === ".") {                spaces.push(pair_to_index(i, j));            } else {                rows[i][char] = true;                columns[j][char] = true;                subboxes[Math.floor(i / 3)][Math.floor(j / 3)][char] = true;            }        }    }    if (spaces.length === 0) {        return;    }
    dfs(new Set(spaces), rows, columns, subboxes, board);    return;}function index_to_pair(index: number): [number, number] {    return [Math.floor(index / 9), index % 9];}function pair_to_index(row: number, column: number) {    return column + 9 * row;}function number_char_set(def: boolean): Record<string, boolean> {    return {        1: def,        2: def,        3: def,        4: def,        5: def,        6: def,        7: def,        8: def,        9: def,    };}function dfs(    spaces: Set<number>,    rows: Record<string, boolean>[],    columns: Record<string, boolean>[],    subboxes: Record<string, boolean>[][],    board: string[][],): boolean {    if (spaces.size === 0) {        return true;    }    const spaces_and_chars: [number, number, string[]][] = [];    for (const index of spaces) {        const [row, column] = index_to_pair(index);        const chars = get_available_chars(row, column, rows, columns, subboxes);        if (chars.length === 0) {            return false;        }        spaces_and_chars.push([row, column, chars] as [            number,            number,            string[],        ]);        if (chars.length === 1) {            break;        }    }    let [i, j, chars] = spaces_and_chars[0];    for (const [r, c, h] of spaces_and_chars) {        if (h.length === 0) {            return false;        }
        if (h.length < chars.length) {            [i, j, chars] = [r, c, h];        }        if (chars.length === 1) {            break;        }    }    if (chars.length === 0) {        return false;    }    for (const char of chars.sort(() => Math.random() - 0.5)) {        rows[i][char] = true;
        columns[j][char] = true;
        subboxes[Math.floor(i / 3)][Math.floor(j / 3)][char] = true;
        board[i][j] = char;        spaces.delete(pair_to_index(i, j));        const result = dfs(            spaces,            rows,            columns,            subboxes,            board,        );        if (result) {            return result;        }        rows[i][char] = false;        columns[j][char] = false;        subboxes[Math.floor(i / 3)][Math.floor(j / 3)][char] = false;        spaces.add(pair_to_index(i, j));    }    return false;}
function get_available_chars(    row: number,    column: number,    rows: Record<string, boolean>[],    columns: Record<string, boolean>[],    subboxes: Record<string, boolean>[][],): Array<string> {    const array = Array.from({ length: 9 }).map((_v, i) => String(i + 1));    const charset = new Set(array);    const set1 = rows[row];    const set2 = columns[column];    const set3 = subboxes[Math.floor(row / 3)][Math.floor(column / 3)];    for (const char of array) {        if (set1[char] || set2[char] || set3[char]) {            charset.delete(char);        }    }    return Array.from(charset);}export default solveSudoku;