Skip to content

Instantly share code, notes, and snippets.

@haru01
Created November 25, 2012 22:27
Show Gist options
  • Save haru01/4145680 to your computer and use it in GitHub Desktop.
Save haru01/4145680 to your computer and use it in GitHub Desktop.
sudoku
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using NUnit.Framework;
using NUnit.Framework.Constraints;
namespace sudoku {
[TestFixture]
public class SudokuBoardTest
{
[Test]
public void FillNum ()
{
var target = new Parser(mondaiData()).Read();
target.FillNum();
Assert.That(target.Cell(1,3).Str(), Is.EqualTo("row:1,col:3,num:4"));
Assert.That(target.Row(1).Select(x => x.num) , Is.EqualTo(new []{ 5,3,4,6,7,8,9,1,2 }));
Assert.That(target.Row(2).Select(x => x.num) , Is.EqualTo(new []{ 6,7,2,1,9,5,3,4,8 }));
Assert.That(target.Row(3).Select(x => x.num) , Is.EqualTo(new []{ 1,9,8,3,4,2,5,6,7 }));
Assert.That(target.Row(4).Select(x => x.num) , Is.EqualTo(new []{ 8,5,9,7,6,1,4,2,3 }));
Assert.That(target.Row(5).Select(x => x.num) , Is.EqualTo(new []{ 4,2,6,8,5,3,7,9,1 }));
Assert.That(target.Row(6).Select(x => x.num) , Is.EqualTo(new []{ 7,1,3,9,2,4,8,5,6 }));
Assert.That(target.Row(7).Select(x => x.num) , Is.EqualTo(new []{ 9,6,1,5,3,7,2,8,4 }));
Assert.That(target.Row(8).Select(x => x.num) , Is.EqualTo(new []{ 2,8,7,4,1,9,6,3,5 }));
Assert.That(target.Row(9).Select(x => x.num) , Is.EqualTo(new []{ 3,4,5,2,8,6,1,7,9 }));
}
[Test]
public void Load ()
{
var target = new Parser(mondaiData()).Read();
Assert.That(target.Cells().Count(), Is.EqualTo(9 * 9));
Assert.That(target.Cell(1,1).Str(), Is.EqualTo("row:1,col:1,num:5"));
Assert.That(target.Row(1).Select(x => x.num) , Is.EqualTo(new []{ 5,3,0,0,7,0,0,0,0 }));
Assert.That(target.Row(9).Select(x => x.num) , Is.EqualTo(new []{ 0,0,0,0,8,0,0,7,9 }));
Assert.That(target.Column(1).Select(x => x.num) , Is.EqualTo(new []{ 5,6,0,8,4,7,0,0,0 }));
Assert.That(target.Column(9).Select(x => x.num) , Is.EqualTo(new []{ 0,0,0,3,1,6,0,5,9 }));
}
[Test]
public void Block ()
{
var target = new Parser(kaitoData()).Read();
Assert.That(target.Block(1,1).Select(x => x.num), Is.EqualTo(new []{ 5,3,4,6,7,2,1,9,8 }));
Assert.That(target.Block(1,3).Select(x => x.num), Is.EqualTo(new []{ 5,3,4,6,7,2,1,9,8 }));
Assert.That(target.Block(3,1).Select(x => x.num), Is.EqualTo(new []{ 5,3,4,6,7,2,1,9,8 }));
Assert.That(target.Block(3,3).Select(x => x.num), Is.EqualTo(new []{ 5,3,4,6,7,2,1,9,8 }));
Assert.That(target.Block(1,4).Select(x => x.num), Is.EqualTo(new []{ 6,7,8,1,9,5,3,4,2 }));
Assert.That(target.Block(1,7).Select(x => x.num), Is.EqualTo(new []{ 9,1,2,3,4,8,5,6,7 }));
Assert.That(target.Block(4,1).Select(x => x.num), Is.EqualTo(new []{ 8,5,9,4,2,6,7,1,3 }));
Assert.That(target.Block(4,4).Select(x => x.num), Is.EqualTo(new []{ 7,6,1,8,5,3,9,2,4 }));
Assert.That(target.Block(4,7).Select(x => x.num), Is.EqualTo(new []{ 4,2,3,7,9,1,8,5,6 }));
Assert.That(target.Block(7,1).Select(x => x.num), Is.EqualTo(new []{ 9,6,1,2,8,7,3,4,5 }));
Assert.That(target.Block(7,4).Select(x => x.num), Is.EqualTo(new []{ 5,3,7,4,1,9,2,8,6 }));
Assert.That(target.Block(7,7).Select(x => x.num), Is.EqualTo(new []{ 2,8,4,6,3,5,1,7,9 }));
}
[Test]
public void RowPossibleNumsByRow ()
{
var target = new Parser(sampleData()).Read();
Assert.That (target.Cell(1,8).PossibleNumsByRow(), Is.EqualTo(new int[]{1, 2}));
}
[Test]
public void RowPossibleNumsByColumn ()
{
var target = new Parser(sampleData()).Read();
Assert.That (target.Cell(1,8).PossibleNumsByColumn(), Is.EqualTo(new int[]{1,5,9}));
}
[Test]
public void RowPossibleNumsByBlock ()
{
var target = new Parser(sampleData()).Read();
Assert.That (target.Cell(1,8).PossibleNumsByBlock(), Is.EqualTo(new int[]{1, 2, 5}));
}
[Test]
public void RowPossibleNums ()
{
var target = new Parser(sampleData()).Read();
Assert.That (target.Cell(1,8).PossibleNums(), Is.EqualTo(new int[]{1}));
Assert.That (target.Cell(1,1).PossibleNums(), Is.EqualTo(new int[]{}));
}
private string mondaiData ()
{
return @"5,3,x,x,7,x,x,x,x
6,x,x,1,9,5,x,x,x
x,9,8,x,x,x,x,6,x
8,x,x,x,6,x,x,x,3
4,x,x,8,x,3,x,x,1
7,x,x,x,2,x,x,x,6
x,6,x,x,x,x,2,8,x
x,x,x,4,1,9,x,x,5
x,x,x,x,8,x,x,7,9";
}
private string kaitoData ()
{
return @"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";
}
private string sampleData ()
{
return @"5,3,4,6,7,8,9,x,x
6,7,2,1,9,5,3,4,8
1,9,8,3,4,2,x,6,7
8,5,9,7,6,1,4,2,3
4,2,6,8,5,3,7,x,1
7,1,3,9,2,4,8,x,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";
}
}
public class Parser {
private readonly string data;
public Parser (string data)
{
this.data = data;
}
public Board Read ()
{
var cells = new List<Cell>();
var board = new Board(cells);
foreach (var line in data.Split('\n').Select((v,i) => new {v, i})) {
foreach(var num in line.v.Split(',').Select((v, j) => new {v, j})) {
cells.Add (new Cell(row: line.i + 1, col: num.j + 1, num: num.v, board: board));
}
}
return board;
}
}
public class Board {
private List<Cell> cells;
public Board(List<Cell> cells) {
this.cells = cells;
}
public Cell Cell (int row, int col)
{
return cells.First(c => c.row == row && c.col == col);
}
public List<Cell> Cells ()
{
return cells;
}
public List<Cell> Row (int rowNum)
{
return cells.Where(c => c.row == rowNum).ToList();
}
public List<Cell> Column (int colNum)
{
return cells.Where(c => c.col == colNum).ToList();
}
public List<Cell> Block (int row, int col)
{
// ATODE
var blockKeys = new[] {
new BlockKey(minRow:1, maxRow:3, minCol:1, maxCol:3),
new BlockKey(minRow:1, maxRow:3, minCol:4, maxCol:6),
new BlockKey(minRow:1, maxRow:3, minCol:7, maxCol:9),
new BlockKey(minRow:4, maxRow:6, minCol:1, maxCol:3),
new BlockKey(minRow:4, maxRow:6, minCol:4, maxCol:6),
new BlockKey(minRow:4, maxRow:6, minCol:7, maxCol:9),
new BlockKey(minRow:7, maxRow:9, minCol:1, maxCol:3),
new BlockKey(minRow:7, maxRow:9, minCol:4, maxCol:6),
new BlockKey(minRow:7, maxRow:9, minCol:7, maxCol:9),
};
var key = blockKeys.First(k => (k.minRow <= row && row <= k.maxRow) &&
(k.minCol <= col && col <= k.maxCol));
return cells.Where(c => key.IsInclude(c) ).ToList();
}
public void FillNum ()
{
while(!IsFillNum()) {
cells = cells.Aggregate(new List<Cell>(), (n, c) => {
n.Add(c.TryFillNum());
return n;
});
}
}
public bool IsFillNum ()
{
return cells.Where(c => c.IsNotFillNum() ).Count() == 0;
}
}
public class BlockKey {
public readonly int minRow;
public readonly int maxRow;
public readonly int minCol;
public readonly int maxCol;
public BlockKey (int minRow, int maxRow, int minCol, int maxCol)
{
this.minRow = minRow; this.maxRow = maxRow; this.minCol = minCol; this.maxCol = maxCol;
}
public bool IsInclude(Cell c)
{
return (minRow <= c.row && c.row <= maxRow) &&
(minCol <= c.col && c.col <= maxCol);
}
}
public class Cell {
public const int UNKNOWN = 0;
public readonly int row;
public readonly int col;
public readonly int num;
public Board board;
public Cell (int row, int col, string num, Board board)
{
this.row = row;
this.col = col;
this.board = board;
try {
this.num = int.Parse(num);
} catch (FormatException) {
this.num = UNKNOWN;
}
}
public Cell (int row, int col, int num, Board board)
{
this.row = row;
this.col = col;
this.board = board;
this.num = num;
}
public bool IsNotFillNum ()
{
return this.num == UNKNOWN;
}
public Cell TryFillNum ()
{
if (1 <= num && num <= 9) {
return this;
}
var possibleNums = PossibleNums().ToArray();
if (possibleNums.Count () != 1) {
return this;
}
return new Cell(row, col, possibleNums[0], board);
}
public IEnumerable<int> PossibleNums ()
{
return PossibleNumsByRow().Intersect(PossibleNumsByColumn()).Intersect(PossibleNumsByBlock());
}
public IEnumerable<int> PossibleNumsByRow ()
{
return OneToNine ().Except(board.Row(row).Select(c => c.num));
}
public IEnumerable<int> PossibleNumsByColumn ()
{
return OneToNine ().Except(board.Column(col).Select(c => c.num));
}
public IEnumerable<int> PossibleNumsByBlock ()
{
return OneToNine ().Except(board.Block(row, col).Select(c => c.num));
}
public IEnumerable<int> OneToNine ()
{
return Enumerable.Range(1, 9);
}
public string Str ()
{
return "row:" + row + ",col:" + col + ",num:" + num;
}
}
public class MainClass {
public static void Main ()
{
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment