ナンプレとは
ナンプレは、Number Placeの略で、9×9の正方形の枠内に、以下の規則にしたがって1〜9までの数字を入れていくパズルです。
- 縦9列のどの列にも1～9の数字がひとつずつはいる
- 横9行のどの行にも1～9の数字がひとつずつはいる
- 正方形内で区切られた3ｘ3のブロック（全部で9つ）のどのブロックにも1～9の数字が1つずつはいる
C#でナンプレを解くプログラムを書く
このパズルを解くのにいわゆるバックトラック法といわれる手法で解を求めています。その中心となるクラスが、Solverクラスです。コードは、この記事の後半で掲載しています。
「マスに数字を置けるか?」とか「マスに数字を置く」などの操作は、すべてBoardクラスが担当していますので、Solverクラスは、とてもシンプルです。
ちなみに、バックトラック法としてはかなりオーソドックスなコードだと思います。特に高速化のための工夫などはしていません。それでも、そこそこの速度は出ています。最後に示したテストデータの場合は、ほぼ待ち時間なく解が求まります。
マスの空きが少ないブロック、行、列から攻めていくようにすれば、もう少し速度が上がると思いますが、そのコードを書くのが面倒なので手抜きしてます。
なお、すべての解を求めるようにしています。なので、解がものすごく多いデータを与えると、いつまでたっても終わらない可能性があります。
もし、一つだけ解を求めたい場合は、Mainメソッドで、
var answer = sol.Solve(nums).Take(1);
のようにすれば、OKです。
データはファイルから読み取るようになっています。
C#のコード
以下、すべてのソースコードです。(GitHubでも公開しています)
Program.cs
データを読み込み、SolverクラスのSolveメソッドを呼び出し解（複数）を求めて、その結果を表示しています。
using System;
using System.Linq;
using System.IO;
namespace NumberPlace {
class Program {
static void Main(string[] args) {
var nums = ReadData(@"data.txt");
var sol = new Solver();
var answer = sol.Solve(nums);
foreach (var board in answer)
board.Print();
}
// データを読み込む
static int[,] ReadData(string path) {
int[,] nums = new int[9, 9];
var lines = File.ReadAllLines(path);
for (int y = 0; y < 9; y++) {
int x = 0;
foreach (var n in lines[y].Split(',')) {
nums[x++, y] = int.Parse(n);
}
}
return nums;
}
}
}
Solver.cs
空いている箇所に条件にあう数字があれば、その数字を置く、という処理を再帰的に繰り返しています。条件に合う数字がない場合には、その手は失敗なので、逆戻りして、別の数字を置くようにしています。
空いている場所はどこかとか、指定した数字が置けるかといった処理は、Boardクラスが担当しています。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace NumberPlace {
class Solver {
private Board _board;
public IEnumerable<Board> Solve(int[,] mat) {
_board = new Board(mat);
return SolveInner();
}
private IEnumerable<Board> SolveInner() {
if (_board.IsCompleted()) {
// 完成したら、answerに答えを入れる。
yield return _board.Clone();
} else {
// 空いている位置をひとつ取り出す
var pos = _board.AlloLocations()
.Where(p => _board.IsVacant(p))
.First();
// そこに、1-9 の数を置いてみる。
for (int n = 1; n <= 9; n++) {
if (_board.CanPut(pos, n)) {
_board.Put(pos, n);
// 置けたので、再帰的に次の数を置いていく。
var answer = SolveInner();
foreach (var a in answer)
yield return a;
// 次の数を置くために、今置いた場所には 0 を入れなおす。
_board.Put(pos, 0);
}
}
// 1..9どれも駄目。つまり失敗-> 呼び出し元に戻る
}
}
}
}
Location.cs
位置を示すクラスです。
using System;
using System.Collections.Generic;
using System.Text;
namespace NumberPlace {
class Location {
public int X { get; set; }
public int Y { get; set; }
public Location(int x, int y) {
X = x;
Y = y;
}
}
}
Board.cs
9×9の正方形を表すクラスで、この正方形に関わる様々なメソッドを定義しています。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace NumberPlace {
class Board {
private int[,] sheet;
// コンストラクタ
public Board(int[,] mat) {
this.sheet = mat;
}
// コンストラクタ
private Board() {
sheet = new int[9, 9];
}
// クローン
public Board Clone() {
var nboard = new Board();
nboard.sheet = (int[,])this.sheet.Clone();
return nboard;
}
// チェックはしない CanPutを呼び出しているのが前提
public void Put(Location pos, int num) {
sheet[pos.X, pos.Y] = num;
}
// 置けるか
public bool CanPut(Location pos, int num) {
if (sheet[pos.X, pos.Y] != 0)
return false;
// 仮に置いてみる。
sheet[pos.X, pos.Y] = num;
try {
return IsValid(pos);
} finally {
// 元に戻す
sheet[pos.X, pos.Y] = 0;
}
}
// 完成か
public bool IsCompleted() {
if (!Enumerable.Range(0, 9).All(nums => IsCompleted(VerticalNums(nums))))
return false;
if (!Enumerable.Range(0, 9).All(nums => IsCompleted(HorizontalNums(nums))))
return false;
return BoxLocations().All(pos => IsCompleted(BoxNums(pos)));
}
// 完成したか
public bool IsCompleted(IEnumerable<int> nums) {
return nums.Where(n => n >= 1).Distinct().Count() == 9;
}
// 空いているか
public bool IsVacant(Location pos) {
return sheet[pos.X, pos.Y] == 0;
}
// posの位置に関する配置は違反していないか
public bool IsValid(Location pos) {
return IsValid(VerticalNums(pos.X)) &&
IsValid(HorizontalNums(pos.Y)) &&
IsValid(BoxNums(pos));
}
// numsに重複はないか （つまり違反していないか）IsCompletedとは別。
public bool IsValid(IEnumerable<int> nums) {
return nums.Where(n => n >= 1).Distinct().Count() == nums.Where(n => n >= 1).Count();
}
// ９つある小さな四角形の左上のLocationを列挙
public IEnumerable<Location> BoxLocations() {
return from x in Enumerable.Range(0, 2)
from y in Enumerable.Range(0, 2)
select new Location(x * 3, y * 3);
}
// 注目している位置が含まれる3*3の領域の数を列挙
public IEnumerable<int> BoxNums(Location pos) {
return from x in Enumerable.Range(0, 3)
from y in Enumerable.Range(0, 3)
select sheet[pos.X / 3 * 3 + x, pos.Y / 3 * 3 + y];
}
// 注目している位置が含まれる縦一列の数を列挙
public IEnumerable<int> VerticalNums(int x) {
for (int y = 0; y < 9; y++) {
yield return sheet[x, y];
}
}
// 注目している位置が含まれる横一列の数を列挙
public IEnumerable<int> HorizontalNums(int y) {
for (int x = 0; x < 9; x++) {
yield return sheet[x, y];
}
}
// すべての位置を列挙する
public IEnumerable<Location> AlloLocations() {
return from x in Enumerable.Range(0, 9)
from y in Enumerable.Range(0, 9)
select new Location(x, y);
}
internal void Print() {
for (int y = 0; y < 9; y++) {
for (int x = 0; x < 9; x += 3) {
Console.Write(" {0} {1} {2}", sheet[x, y], sheet[x+1, y], sheet[x+2, y]);
if (x == 0 || x == 3)
Console.Write("|");
}
Console.WriteLine();
if (y == 2 || y == 5)
Console.WriteLine("------+------+------");
}
Console.WriteLine();
}
}
}
実行結果
以下の示すデータを与えて、解いてみました。データの0は空いていることを示しています。
ここでは、あえて、複数の解を持つ問題を解かせてみました。
入力データ
0,2,0,0,7,5,0,1,0
1,0,0,0,0,4,5,0,8
0,5,6,8,0,0,2,0,0
8,1,0,0,0,0,7,0,0
9,0,0,0,0,0,0,0,3
0,0,2,0,0,0,0,4,5
0,0,9,0,0,1,4,3,0
3,0,1,7,0,0,0,0,9
0,7,0,3,9,0,0,2,0
解
4 2 8| 9 7 5| 3 1 6
1 9 3| 2 6 4| 5 7 8
7 5 6| 8 1 3| 2 9 4
------+------+------
8 1 5| 4 3 9| 7 6 2
9 4 7| 5 2 6| 1 8 3
6 3 2| 1 8 7| 9 4 5
------+------+------
2 8 9| 6 5 1| 4 3 7
3 6 1| 7 4 2| 8 5 9
5 7 4| 3 9 8| 6 2 1
4 2 8| 9 7 5| 3 1 6
1 9 3| 6 2 4| 5 7 8
7 5 6| 8 1 3| 2 9 4
------+------+------
8 1 5| 4 3 9| 7 6 2
9 4 7| 2 5 6| 1 8 3
6 3 2| 1 8 7| 9 4 5
------+------+------
2 8 9| 5 6 1| 4 3 7
3 6 1| 7 4 2| 8 5 9
5 7 4| 3 9 8| 6 2 1
２つの解が求まりました。