Skip to content

Commit 1178818

Browse files
JRaspassJRaspass
committed
Add "Sudoku" hole
Updates #3 Needs to switch to dancing links to fix a todo, but will do for now.
1 parent db5cba8 commit 1178818

File tree

5 files changed

+243
-0
lines changed

5 files changed

+243
-0
lines changed

‎db.sql‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -47,6 +47,7 @@ CREATE TYPE public.hole AS ENUM (
4747
'seven-segment',
4848
'sierpiński-triangle',
4949
'spelling-numbers',
50+
'sudoku',
5051
'λ',
5152
'π',
5253
'τ',

‎routes/home.go‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -129,6 +129,7 @@ func home(w http.ResponseWriter, r *http.Request, _ httprouter.Params) {
129129
WHEN 'roman-to-arabic' THEN 29
130130
WHEN 'rule-110' THEN 30
131131
WHEN 'spelling-numbers' THEN 31
132+
WHEN 'sudoku' THEN 32
132133
END, row_number`,
133134
userID,
134135
)

‎routes/solution.go‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -55,6 +55,8 @@ func solution(w http.ResponseWriter, r *http.Request, _ httprouter.Params) {
5555
args[0], out.Exp = sevenSegment()
5656
case "spelling-numbers":
5757
args, out.Exp = spellingNumbers()
58+
case "sudoku":
59+
args, out.Exp = sudoku()
5860
default:
5961
out.Exp = answers[in.Hole]
6062
}

‎routes/sudoku.go‎

Lines changed: 217 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,217 @@
1+
package routes
2+
3+
import (
4+
"math/rand"
5+
"strings"
6+
)
7+
8+
const boardSize = 9
9+
const blockSize = 3
10+
11+
func solve(board [boardSize][boardSize]int, cell int, count *int) bool {
12+
var i, j int
13+
14+
for {
15+
if cell == boardSize*boardSize {
16+
*count++
17+
if *count == 2 {
18+
return true
19+
} else {
20+
return false
21+
}
22+
}
23+
24+
i = cell / boardSize
25+
j = cell % boardSize
26+
27+
if board[i][j] == 0 {
28+
break
29+
}
30+
31+
cell++
32+
}
33+
34+
// Origin of block.
35+
i0 := i - i%blockSize
36+
j0 := j - j%blockSize
37+
38+
// 1 - 9 in random order.
39+
var numbers [boardSize]int
40+
41+
for i := range numbers {
42+
j := rand.Intn(i + 1)
43+
numbers[i] = numbers[j]
44+
numbers[j] = i + 1
45+
}
46+
47+
Numbers:
48+
for _, number := range numbers {
49+
// number is already in the row.
50+
for _, numberInRow := range board[i] {
51+
if number == numberInRow {
52+
continue Numbers
53+
}
54+
}
55+
56+
// number is already in the column.
57+
for _, row := range board {
58+
if number == row[j] {
59+
continue Numbers
60+
}
61+
}
62+
63+
// number is already in the block.
64+
for _, row := range board[i0:i] {
65+
for _, numberInRow := range row[j0 : j0+blockSize] {
66+
if number == numberInRow {
67+
continue Numbers
68+
}
69+
}
70+
}
71+
72+
board[i][j] = number
73+
74+
if solve(board, cell+1, count) {
75+
return true
76+
}
77+
}
78+
79+
// No valid number for this cell, let's backtrack.
80+
board[i][j] = 0
81+
82+
return false
83+
}
84+
85+
func sudoku() (args []string, out string) {
86+
var board [boardSize][boardSize]int
87+
88+
var generate func(int) bool
89+
generate = func(cell int) bool {
90+
i := cell / boardSize
91+
j := cell % boardSize
92+
93+
// Origin of block.
94+
i0 := i - i%blockSize
95+
j0 := j - j%blockSize
96+
97+
// 1 - 9 in random order.
98+
var numbers [boardSize]int
99+
100+
for i := range numbers {
101+
j := rand.Intn(i + 1)
102+
numbers[i] = numbers[j]
103+
numbers[j] = i + 1
104+
}
105+
106+
Numbers:
107+
for _, number := range numbers {
108+
// number is already in the row.
109+
for _, numberInRow := range board[i] {
110+
if number == numberInRow {
111+
continue Numbers
112+
}
113+
}
114+
115+
// number is already in the column.
116+
for _, row := range board {
117+
if number == row[j] {
118+
continue Numbers
119+
}
120+
}
121+
122+
// number is already in the block.
123+
for _, row := range board[i0:i] {
124+
for _, numberInRow := range row[j0 : j0+blockSize] {
125+
if number == numberInRow {
126+
continue Numbers
127+
}
128+
}
129+
}
130+
131+
board[i][j] = number
132+
133+
if cell+1 == boardSize*boardSize || generate(cell+1) {
134+
return true
135+
}
136+
}
137+
138+
// No valid number for this cell, let's backtrack.
139+
board[i][j] = 0
140+
141+
return false
142+
}
143+
144+
generate(0)
145+
146+
var b strings.Builder
147+
148+
for i, row := range board {
149+
if i == 0 {
150+
b.WriteString("┏━━━┯━━━┯━━━┳━━━┯━━━┯━━━┳━━━┯━━━┯━━━┓\n")
151+
} else if i%blockSize == 0 {
152+
b.WriteString("┣━━━┿━━━┿━━━╋━━━┿━━━┿━━━╋━━━┿━━━┿━━━┫\n")
153+
} else {
154+
b.WriteString("┠───┼───┼───╂───┼───┼───╂───┼───┼───┨\n")
155+
}
156+
157+
for j, number := range row {
158+
if j%blockSize == 0 {
159+
b.WriteString("┃")
160+
} else {
161+
b.WriteString("│")
162+
}
163+
164+
b.WriteRune(' ')
165+
if number == 0 {
166+
b.WriteRune(' ')
167+
} else {
168+
b.WriteRune(rune('0' + number))
169+
}
170+
b.WriteRune(' ')
171+
}
172+
173+
b.WriteString("┃\n")
174+
}
175+
176+
b.WriteString("┗━━━┷━━━┷━━━┻━━━┷━━━┷━━━┻━━━┷━━━┷━━━┛")
177+
178+
out = b.String()
179+
180+
for k, cell := range rand.Perm(boardSize * boardSize) {
181+
i := cell / boardSize
182+
j := cell % boardSize
183+
184+
orig := board[i][j]
185+
board[i][j] = 0
186+
187+
var count int
188+
solve(board, 0, &count)
189+
190+
// Removing this cell creates too many solutions, put it back.
191+
if count == 2 {
192+
board[i][j] = orig
193+
}
194+
195+
// TODO Switch to dancing links to remove this grotesque hack!
196+
// http://garethrees.org/2007/06/10/zendoku-generation/#section-4
197+
if k == 50 {
198+
break
199+
}
200+
}
201+
202+
for _, row := range board {
203+
var b strings.Builder
204+
205+
for _, number := range row {
206+
if number == 0 {
207+
b.WriteRune('_')
208+
} else {
209+
b.WriteRune(rune('0' + number))
210+
}
211+
}
212+
213+
args = append(args, b.String())
214+
}
215+
216+
return
217+
}

‎routes/types.go‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -204,6 +204,28 @@ A Partridge in a Pear Tree.</blockquote>`,
204204
"", "",
205205
"spelling-numbers", "Spelling Numbers", "Slow",
206206
"For each number argument print the same number spelled out in English.<p>The numbers will be in the range of <b>0</b> to <b>1,000</b> inclusive.</p>",
207+
}, {
208+
"", "",
209+
"sudoku", "Sudoku", "Slow",
210+
`Sudoku is a number puzzle where a grid of 81 digits (9x9) is filled by the digits 1-9 such that no row, column, or 3x3 subregion contains duplicate digits.<p>Write a program that given an incomplete Sudoku board as 9 arguments of 9 digits, with blanks respresented by an underscore, print a solved Sudoku grid using unicode box-drawing characters like so:<pre>┏━━━┯━━━┯━━━┳━━━┯━━━┯━━━┳━━━┯━━━┯━━━┓
211+
┃ 2 │ 5 │ 8 ┃ 4 │ 1 │ 7 ┃ 6 │ 9 │ 3 ┃
212+
┠───┼───┼───╂───┼───┼───╂───┼───┼───┨
213+
┃ 6 │ 1 │ 7 ┃ 9 │ 2 │ 3 ┃ 8 │ 5 │ 4 ┃
214+
┠───┼───┼───╂───┼───┼───╂───┼───┼───┨
215+
┃ 9 │ 3 │ 4 ┃ 8 │ 6 │ 5 ┃ 1 │ 7 │ 2 ┃
216+
┣━━━┿━━━┿━━━╋━━━┿━━━┿━━━╋━━━┿━━━┿━━━┫
217+
┃ 3 │ 2 │ 5 ┃ 7 │ 8 │ 1 ┃ 4 │ 6 │ 9 ┃
218+
┠───┼───┼───╂───┼───┼───╂───┼───┼───┨
219+
┃ 8 │ 9 │ 6 ┃ 3 │ 5 │ 4 ┃ 2 │ 1 │ 7 ┃
220+
┠───┼───┼───╂───┼───┼───╂───┼───┼───┨
221+
┃ 7 │ 4 │ 1 ┃ 6 │ 9 │ 2 ┃ 5 │ 3 │ 8 ┃
222+
┣━━━┿━━━┿━━━╋━━━┿━━━┿━━━╋━━━┿━━━┿━━━┫
223+
┃ 4 │ 6 │ 9 ┃ 1 │ 3 │ 8 ┃ 7 │ 2 │ 5 ┃
224+
┠───┼───┼───╂───┼───┼───╂───┼───┼───┨
225+
┃ 5 │ 7 │ 3 ┃ 2 │ 4 │ 6 ┃ 9 │ 8 │ 1 ┃
226+
┠───┼───┼───╂───┼───┼───╂───┼───┼───┨
227+
┃ 1 │ 8 │ 2 ┃ 5 │ 7 │ 9 ┃ 3 │ 4 │ 6 ┃
228+
┗━━━┷━━━┷━━━┻━━━┷━━━┷━━━┻━━━┷━━━┷━━━┛</pre>`,
207229
}, {
208230
"", "",
209231
"λ", "λ", "Medium",

0 commit comments

Comments
 (0)