85 lines
2.2 KiB
Text
85 lines
2.2 KiB
Text
local buffer = require "pluto:buffer"
|
|
|
|
class sudoku
|
|
private grid, solved
|
|
|
|
-- Use 0-based indexing for the grid.
|
|
function __construct(rows)
|
|
if #rows != 9 or !rows:checkall(|r| -> #r == 9) then
|
|
error("Grid must be 9 x 9")
|
|
end
|
|
self.grid = {}
|
|
for i = 0, 8 do
|
|
for j = 0, 8 do self.grid[9 * i + j] = rows[i + 1][j + 1] end
|
|
end
|
|
self.solved = false
|
|
end
|
|
|
|
private function check_validity(v, x, y)
|
|
for i = 0, 8 do
|
|
if self.grid[y * 9 + i] == v or self.grid[i * 9 + x] == v then
|
|
return false
|
|
end
|
|
end
|
|
local start_x = (x // 3) * 3
|
|
local start_y = (y // 3) * 3
|
|
for i = start_y, start_y + 2 do
|
|
for j = start_x, start_x + 2 do
|
|
if self.grid[i * 9 + j] == v then return false end
|
|
end
|
|
end
|
|
return true
|
|
end
|
|
|
|
private function place_number(pos)
|
|
if self.solved then return end
|
|
if pos == 81 then
|
|
self.solved = true
|
|
return
|
|
end
|
|
if self.grid[pos] > "0" then
|
|
self:place_number(pos + 1)
|
|
return
|
|
end
|
|
for n = 1, 9 do
|
|
if self:check_validity(tostring(n), pos % 9, pos // 9) do
|
|
self.grid[pos] = tostring(n)
|
|
self:place_number(pos + 1)
|
|
if self.solved then return end
|
|
self.grid[pos] = "0"
|
|
end
|
|
end
|
|
end
|
|
|
|
function solve()
|
|
print($"Starting grid:\n\n{self}")
|
|
self:place_number(0)
|
|
print(self.solved ? $"Solution:\n\n{self}" : "Unsolvable!")
|
|
end
|
|
|
|
function __tostring()
|
|
local sb = new buffer()
|
|
for i = 0, 8 do
|
|
for j = 0, 8 do
|
|
sb:append(self.grid[i * 9 + j] .. " ")
|
|
if j == 2 or j == 5 then sb:append("| ") end
|
|
end
|
|
sb:append("\n")
|
|
if i == 2 or i == 5 then sb:append("------+-------+------\n") end
|
|
end
|
|
return sb:tostring()
|
|
end
|
|
end
|
|
|
|
local rows = {
|
|
"850002400",
|
|
"720000009",
|
|
"004000000",
|
|
"000107002",
|
|
"305000900",
|
|
"040000000",
|
|
"000080070",
|
|
"017000000",
|
|
"000036040"
|
|
}
|
|
new sudoku(rows):solve()
|