数独を解くプログラム

質問

私は、ナンプレ(数独)が好きでよく問題を解いています。
ふと、(以前少しだけＣ言語の勉強をしていたので)Ｃ言語でナンプレを解くプログラムを作るとしたらどんなソースになるのか気になりました。
私自身のプログラム理解のレベルがソースをかなりゆっくり読んで理解できる程度なので、プログラムにおこすことなど、とてもできません。
また、過去の質問を検索してみましたがJavaやＣ＃のものは見つけられましたが、Ｃは見つけられませんでした。
面倒だとは思いますが、よろしければご教授ください。

回答No.4

tadokiro

9行9列のスタンダード限定ですが虱潰しをするソースが載ってます。

参考URL：

http://www.mediatips.co.jp/puzzle-9x9.html

回答No.3

chie65536（@chie65535）

９×９の配列を用意して、それを処理します。

配列の各要素には
０＝空欄
１～９＝埋まっている数字
－１～－９＝置けない場所
を入れます。

そして
１．配列の中で１が置けない場所を－１で埋める
２．縦、横、３×３の枠で、０（空欄）が１つだけになったら、そこに１を入れる
３．配列の中の－１を０に戻す
４．配列の中で２が置けない場所を－２で埋める
５．縦、横、３×３の枠で、０（空欄）が１つだけになったら、そこに２を入れる
６．配列の中の－２を０に戻す
７．上記１～３、４～６の手順で、３～９までの数字を処理する
８．数字を１～９まで処理し、すべての枠が埋まったら完成。まだ空欄があるなら最初からやり直す
９．まだ空欄があって最初からやり直しても変化しないなら、置ける数字を置けそうな場所に置いて、試してみる

上記の処理をプログラムしてみたのが、以下のプログラムです。

#define true 1
#define false 0

//例題がセットしてあります
//ReadMap()の中身が無くても
//例題を解く事が出来ます
char map[9][9] = {
0,0,0,0,3,2,0,0,0,
0,3,0,6,0,4,0,5,0,
0,0,7,0,0,0,1,0,0,
6,8,0,0,0,0,0,7,0,
2,0,0,0,8,0,0,0,3,
0,9,0,0,0,0,0,1,4,
0,0,3,0,0,0,5,0,0,
0,6,0,3,0,5,0,2,0,
0,0,0,8,1,0,0,0,0
};

void ReadMap(void)
{
//ファイルから読んでmap配列にセットする関数
//自分で作りましょう
}

int CheckMap(int x,int y,int n)
{
int i,j,ii,jj;
for (i = 0;i < 9;i++) {
if ((i != y) && (map[x][i] == n)) return false;
if ((i != x) && (map[i][y] == n)) return false;
}
ii = x - (x % 3);
jj = y - (y % 3);
for (i = 0;i < 3;i++) {
for (j = 0;j < 3;j++) {
if ((x != ii+i) && (y != jj+j) && (map[ii+i][jj+j] == n)) return false;
}
}
return true;
}

void SetMask(int n)
{
int i,j,ii,jj,iii,jjj;
for(i = 0;i < 9;i++) {
for(j = 0;j < 9;j++) {
if (map[i][j] == n) {
for(ii=0;ii < 9;ii++) {
if (map[ii][j] == 0) map[ii][j] = (char)-n;
if (map[i][ii] == 0) map[i][ii] = (char)-n;
}
iii = i - (i % 3);
jjj = j - (j % 3);
for(ii = 0;ii < 3;ii++) {
for(jj = 0;jj < 3;jj++) {
if (map[iii+ii][jjj+jj] == 0) map[iii+ii][jjj+jj] = (char)-n;
}
}
}
}
}
}

int AnswerMake(void)
{
int e;
int p;
int n;
int i,j,ii,jj;
e = true;
for (;;) {
int f = 0;
for(n = 1;n <= 9;n++) {
SetMask(n);
for(i = 0;i < 9;i++) {
p = 0;
for(j = 0;j < 9;j++) {
if (map[i][j] == n) {
p = -1;
break;
}
if (map[i][j] == 0) {
p++;
ii = i;
jj = j;
}
}
if (p == 1) {
map[ii][jj] = (char)n;
SetMask(n);
f++;
}
if (!p) {
e = false;
}
}
for(i = 0;i < 9;i++) {
p = 0;
for(j = 0;j < 9;j++) {
if (map[j][i] == n) {
p = -1;
break;
}
if (map[j][i] == 0) {
p++;
ii = i;
jj = j;
}
}
if (p == 1) {
map[jj][ii] = (char)n;
SetMask(n);
f++;
}
if (!p) {
e = false;
}
}
for(int i = 0;i < 9;i += 3) {
for(int j = 0;j < 9;j += 3) {
p = 0;
bool b = false;
for(iii = 0;iii < 3;iii++) {
for(jjj = 0;jjj < 3;jjj++) {
if (map[i+iii][j+jjj] == n) {
p = -1;
b = true;
break;
}
if (map[i+iii][j+jjj] == 0) {
p++;
ii = i+iii;
jj = j+jjj;
}
}
if (b) break;
}
if (p == 1) {
map[ii][jj] = (char)n;
SetMask(n);
f++;
}
if (!p) {
e = false;
}
}
}
p = 0;
for(i = 0;i < 9;i++) {
for(j = 0;j < 9;j++) {
if (map[i][j] < 0) {
map[i][j] = 0;
}
if (!map[i][j]) {
p++;
}
}
}
}
if (f == 0) break;
}
if (!p) return 0;
if (e) return 1;
return -1;
}

int AnswerSearch(void)
{
int i,j,n,s;
char map2[9][9];
for(i = 0;i < 9;i++) {
for(j = 0;j < 9;j++) {
if (map[i][j] == 0) {
for(n = 1;n <= 9;n++) {
if (CheckMap(i,j,n)) {
memcpy(map2,map,sizeof(map));
map[i][j] = (char)n;
s = AnswerMake();
if (s == 0) {
return 0;
}
if (s > 0) {
s = AnswerSearch();
if (s == 0)
return 0;
}
memcpy(map,map2,sizeof(map));
}
}
return -1;
}
}
}
return 0;
}

void DisplayMap(void)
{
int i,j;
for (i = 0;i < 9;i++) {
for (j = 0;j < 9;j++) {
printf("%3d",map[i][j]);
}
printf("\n");
}
}

int main(void)
{
int s;
ReadMap(); //自分で作りましょう
s = AnswerMake();
if (s > 0) s = AnswerSearch();
if (s < 0) printf("解答が存在しません\n");
if (s > 0) printf("数字を特定できないマスがあります\n");
DisplayMap();
}

回答No.2

toku8

わたしは　ACCESS2000　で
数独の答えが算出できるプログラムを作成して
ナンプレクイズなどで　使用しています
（頭の体操にはなりませんが　答えは瞬時に出ます）

ACCESSｖｂａで組んでいます
ロジックとしては　縦横の既存数字を見て　各コマに
候補（だいたい２－５個ぐらい）数値を表示して
その次に　その状況から見て　確定数字を出せるコマを
プログラムが選び出してそこの数値を確定させる
また　次に　その状況を基にして他のコマを順次確定していく
という方式です
だいたい　５回程度ボタンを押せば全コマ確定します

ごくたまに上級向けの問題では　数値確定できない問題もあります
その場合は　人力で（2つの候補が表示されているコマ）１つの数値
を仮選択して　次の段階へ進むようにしています
（もし選んだほうがミスなら後刻エラーになるので　もういちど
　戻り　別の数値を選んで進める）

回答No.1

wasabifumi

JavaやC#もCから発展したものなので
いくつかの関数は自分で作る必要が出るかもしれませんが
アルゴリズム自体はCに変換可能でしょう。
（数字が入ったオブジェクトを変数に変えるなどが必要でしょう）

ただ、どのような環境でCを使用するかわかりませんが
単純なCではGUIが準備されていないので
どのように数字を入力し、どのように結果を表示するか？
ということを考えなくてはいけません。

お礼

お早い回答、ご指摘ありがとうございます。

数字の入力と結果の表示ですがtxtで問題をあらかじめ用意しておいて、そのファイルを読み込み、そのファイルに追加に書き込み表示する。というファイル操作の方法くらいしか私のレベルでは思い付かないのですが…。

とにかくご回答ありがとうございました。