sudoku

gistfile1.cs

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 ()
		{
		}
	}
}