Skip to content

Instantly share code, notes, and snippets.

@suzuken

suzuken/sudoku.go

Created Jul 4, 2020
Embed
What would you like to do?
2020 Go Live Coding at 技育祭
package main
import (
"bufio"
"bytes"
"errors"
"flag"
"fmt"
"os"
"strconv"
"strings"
)
// Boardはsudokuのboardを示す
//
// 0: 未入力
// 1-9: 入力
type Board [9][9]int
func pretty(b Board) string {
var buf bytes.Buffer
for i := 0; i < 9; i++ {
if i%3 == 0 {
buf.WriteString("+---+---+---+\n")
}
for j := 0; j < 9; j++ {
if j%3 == 0 {
buf.WriteString("|")
}
buf.WriteString(strconv.Itoa(b[i][j]))
}
buf.WriteString("|\n")
}
buf.WriteString("+---+---+---+\n")
return buf.String()
}
func duplicated(c [10]int) bool {
for k, v := range c {
if k == 0 {
continue
}
if v >= 2 {
return true
}
}
return false
}
func verify(b Board) bool {
// 行チェック
for i := 0; i < 9; i++ {
// 出現回数
var c [10]int
for j := 0; j < 9; j++ {
c[b[i][j]]++
}
if duplicated(c) {
return false
}
}
// 行チェック
for i := 0; i < 9; i++ {
// 出現回数
var c [10]int
for j := 0; j < 9; j++ {
c[b[j][i]]++
}
if duplicated(c) {
return false
}
}
// 3x3のチェック
for i := 0; i < 9; i += 3 {
for j := 0; j < 9; j += 3 {
var c [10]int
for row := i; row < i+3; row++ {
for col := j; col < j+3; col++ {
c[b[row][col]]++
}
}
if duplicated(c) {
return false
}
}
}
return true
}
func solved(b Board) bool {
if !verify(b) {
return false
}
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
if b[i][j] == 0 {
return false
}
}
}
return true
}
// backtrace
func backtrack(b *Board) bool {
// time.Sleep(time.Second * 1)
// fmt.Printf("%+v\n", pretty(*b))
if solved(*b) {
return true
}
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
// ますが0
if b[i][j] == 0 {
for c := 9; c >= 1; c-- {
b[i][j] = c
// もし数字がルールに適合するなら
if verify(*b) {
// さらに深く探索する
if backtrack(b) {
return true
}
}
b[i][j] = 0
}
return false
}
}
}
return false
}
// input :.5..83.17...1..4..3.4..56.8....3...9.9.8245....6....7...9....5...729..861.36.72.4
func short(input string) (*Board, error) {
if len(input) != 81 {
return nil, errors.New("input short stringlength must be 81")
}
s := bufio.NewScanner(strings.NewReader(input))
s.Split(bufio.ScanRunes)
var b Board
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
if !s.Scan() {
break
}
token := s.Text()
if token == "." {
b[i][j] = 0
continue
}
n, err := strconv.Atoi(token)
if err != nil {
return nil, err
}
b[i][j] = n
}
}
return &b, nil
}
func main() {
flag.Parse()
input := flag.Arg(0)
fmt.Printf("input = %+v\n", input)
b, err := short(input)
if err != nil {
panic(err)
}
if backtrack(b) {
fmt.Println(pretty(*b))
} else {
fmt.Fprint(os.Stderr, "cannot solve")
}
}
package main
import (
"fmt"
"reflect"
"testing"
)
func TestDupicated(t *testing.T) {
if duplicated([10]int{
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
}) {
t.Fatal("not duplicated but failed")
}
if !duplicated([10]int{
0, 2, 0, 0, 0, 0, 0, 0, 0, 0,
}) {
t.Fatal("its duplicated")
}
}
func TestVerify(t *testing.T) {
cases := []struct {
msg string
b Board
expected bool
}{
{
msg: "all zero",
b: Board{
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
},
expected: true,
},
{
msg: "row check",
b: Board{
{1, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
},
expected: false,
},
{
msg: "col check",
b: Board{
{1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
},
expected: false,
},
{
msg: "box check",
b: Board{
{1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
},
expected: false,
},
}
for k, v := range cases {
t.Run(fmt.Sprintf("#%d %s", k, v.msg), func(t *testing.T) {
got := verify(v.b)
if got != v.expected {
t.Errorf("want %v, got %v", v.expected, got)
}
})
}
}
func TestSolve(t *testing.T) {
// test case from https://github.com/t-dillon/tdoku provided under BSD-2 LICENSE.
// .5..83.17...1..4..3.4..56.8....3...9.9.8245....6....7...9....5...729..861.36.72.4:1:652483917978162435314975628825736149791824563436519872269348751547291386183657294
// .5..83.17...1..4..3.4..56.8....3...9.9.8245....6....7...9....5...729..861.36.72.4
b := Board{
{0, 5, 0, 0, 8, 3, 0, 1, 7},
{0, 0, 0, 1, 0, 0, 4, 0, 0},
{3, 0, 4, 0, 0, 5, 6, 0, 8},
{0, 0, 0, 0, 3, 0, 0, 0, 9},
{0, 9, 0, 8, 2, 4, 5, 0, 0},
{0, 0, 6, 0, 0, 0, 0, 7, 0},
{0, 0, 9, 0, 0, 0, 0, 5, 0},
{0, 0, 7, 2, 9, 0, 0, 8, 6},
{1, 0, 3, 6, 0, 7, 2, 0, 4},
}
if !backtrack(&b) {
t.Fatal("should solve but cannot")
}
fmt.Printf("b = %+v\n", b)
}
func TestShortInput(t *testing.T) {
b, err := short(".5..83.17...1..4..3.4..56.8....3...9.9.8245....6....7...9....5...729..861.36.72.4")
if err != nil {
t.Fatalf("parse failed: %s", err)
}
expected := Board{
{0, 5, 0, 0, 8, 3, 0, 1, 7},
{0, 0, 0, 1, 0, 0, 4, 0, 0},
{3, 0, 4, 0, 0, 5, 6, 0, 8},
{0, 0, 0, 0, 3, 0, 0, 0, 9},
{0, 9, 0, 8, 2, 4, 5, 0, 0},
{0, 0, 6, 0, 0, 0, 0, 7, 0},
{0, 0, 9, 0, 0, 0, 0, 5, 0},
{0, 0, 7, 2, 9, 0, 0, 8, 6},
{1, 0, 3, 6, 0, 7, 2, 0, 4},
}
if reflect.DeepEqual(b, expected) {
t.Fatalf("want %v, got %v", expected, b)
}
{
b, err := short(".")
if b != nil {
t.Fatalf("board should be nil: %s", err)
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.