初めまして。都内の普通高校に通うとものです。
私は今、独学でC++のプログラミングを1年ほど学んでおり、夏の期間を使って趣味の数独の採点プログラムを作ろうと考えておりました。
プログラムを組むにあたり、下記のアルゴリズムを教えていただきたいです。
あるマスに候補数字が一つしかなければそのマスはその候補数字で確定するというロジックです。
下図で○のついた候補数字4のあるマスは4以外の候補数字がないため、このマスは4で確定します。 半角は数独でいうマスに入る可能性の添え字です。
１ ５ 68 １ ５ 68
④ ３ ９ → 4 ３ ９
48 ７ ２ 8 ７ ２
ここでのアルゴリズムを教えていただきたいのですが、どうかご教授いただければ幸いです。
サブブロックごとに別の配列にしてしまうのは手間が増えるだけのような気がします…
//9x9のマスすべてに1-9すべての数字が候補となっている初期状態
//初期化めんどくさい…vectorをnewで作れるんだっけ？
std::vector<std::vector<std::vector<int>>> board{
{//1行目
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9}
},{//2行目
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9}
},{//3行目
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9}
},{//4行目
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9}
},{//5行目
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9}
},{//6行目
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9}
},{//7行目
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9}
},{//8行目
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9}
},{//9行目
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9},{1,2,3,4,5,6,7,8,9}
}
};
この状態から可能性のなくなった候補を削除すると、board[y][x].count == 1となったマスが確定したマスとなるので判定が楽になります。
さらに
//nが候補に残っていればtrue
if(std::find(board[y][x].begin(), board[y][x].end(), n) != board[y][x].end()) { ... }
//nを候補から削除
board[y][x].erase(std::find(board[y][x].begin(), board[y][x].end(), n));
のように書くことができるのでコードが短くなり、本来書きたいアルゴリズムに集中できると思います。
数独を解くやり方を簡単に箇条書きしてみます。
●説明の前提
・データのマス目は[９ｘ９]、サブブロックのマスを[３ｘ３]とします。
・判定用のデータとして、サブブロック内の各マスに[１〜９]の数字に対する除外フラグ(このフラグが立つと対象の数字はそのマスには入らない）をもつとします。
●解き方
１.サブブロック内で、すでに確定している数字に対して、各マスの除外フラグを立てる
２.サブブロック内で、数字が確定しているマスがもつ除外フラグを全て立てる
３.サブブロックと同じ行(ヨコ方向)の確定数字に対して、同行のマスの除外フラグを立てる
４.サブブロックと同じ列(タテ方向)の確定数字に対して、同列のマスの除外フラグを立てる
５.各数字の除外フラグを調べ、１マスだけ除外されていなければ、その数字をそのマスに確定する
言葉で書くと難しいですね。
「正解を探す」のではなく「埋まらないマスを除外していく」という消去法の考えです。
候補をつぶしていって、１つになった数字のマスを埋めると思ってください。
下記、サンプルコードとなります。
// サイズ定義
#define DATA_SIZE 9
#define SUB_SIZE 3
// (subX,subY)で指定されるサブブロック[3x3]を調べる
// [data]は[DATA_SIZE][DATA_SIZE]の二次元配列とみなす
void CTestLoop::checkSubBlockAt( int* data, int subX, int subY ){
// [check]はサブブロックにおける[y][x][1-9の各数字が除外済み？]の三次元配列とみなす
bool check[SUB_SIZE*SUB_SIZE*DATA_SIZE];
for( int i=0; i<SUB_SIZE*SUB_SIZE*DATA_SIZE; i++ ){ check[i] = false; }
// １.サブブロック内で埋まっている数字を候補から除外
// ２.サブブロック内ですでに数字が確定しているマスの候補は全て除外
for( int y=0; y<SUB_SIZE; y++ ){
for( int x=0; x<SUB_SIZE; x++ ){
int target = (subY*SUB_SIZE+y)*DATA_SIZE + (subX*SUB_SIZE+x);
if( data[target] != 0 ){
int ofs = data[target] - 1;
for( int i=0; i<SUB_SIZE*SUB_SIZE; i++ ){
check[i*DATA_SIZE+ofs] = true;
}
for( int i=0; i<DATA_SIZE; i++ ){
check[((y*SUB_SIZE)+x)*DATA_SIZE+i] = true;
}
}
}
}
// ３.サブブロックからヨコ方向に眺めて出現した数字を候補から除外
for( int y=0; y<SUB_SIZE; y++ ){
for( int x=0; x<DATA_SIZE; x++ ){
int target = (subY*SUB_SIZE+y)*DATA_SIZE + x;
if( data[target] != 0 ){
int ofs = data[target] - 1;
for( int i=0; i<SUB_SIZE; i++ ){
check[(y*SUB_SIZE + i)*DATA_SIZE + ofs] = true;
}
}
}
}
// ４.サブブロックからタテ方向に眺めて出現した数字を候補から除外
for( int x=0; x<SUB_SIZE; x++ ){
for( int y=0; y<DATA_SIZE; y++ ){
int target = y*DATA_SIZE + (subX*SUB_SIZE+x);
if( data[target] != 0 ){
int ofs = data[target] - 1;
for( int i=0; i<SUB_SIZE; i++ ){
check[(i*SUB_SIZE + x)*DATA_SIZE + ofs] = true;
}
}
}
}
// ５.サブブロック内で候補が１マスに絞られたら確定
for( int i=0; i<DATA_SIZE; i++ ){
int hitNum = 0;
int hitX = -1;
int hitY = -1;
for( int y=0; y<SUB_SIZE; y++ ){
for( int x=0; x<SUB_SIZE; x++ ){
if( ! check[(y*SUB_SIZE + x)*DATA_SIZE + i] ){
hitNum++;
hitX = x;
hitY = y;
}
}
}
if( hitNum == 1 ){
int target = (subY*SUB_SIZE+hitY)*DATA_SIZE + (subX*SUB_SIZE+hitX);
data[target] = i + 1;
}
}
}
// クリア判定：[data]の全マスが確定していたら[true]
bool CTestLoop::isCorrect( int *data ){
for( int i=0; i<DATA_SIZE*DATA_SIZE; i++ ){
if( data[i] == 0 ){ return( false ); }
}
return( true );
}
// ダンプ：[data]を整形して出力
void CTestLoop::dumpData( int* data ){
printf( "{" );
for( int i=0; i<DATA_SIZE*DATA_SIZE; i++ ){
if( (i%DATA_SIZE) == 0 ){
printf( "\n " );
if( ((i/DATA_SIZE)%SUB_SIZE) == 0 && i > 0){
printf( "\n " );
}
}
printf( "%d ", data[i] );
if( (i%SUB_SIZE) == (SUB_SIZE-1) ){
printf( " " );
}
}
printf( "\n}\n" );
}
// 動作確認
void CTestLoop::test( void ){
// 問題データ（※[0]の値が未確定）
int data[DATA_SIZE*DATA_SIZE] = {
0,0,6, 0,0,0, 0,0,1,
0,7,0, 0,6,0, 0,5,0,
8,0,0, 1,0,3, 2,0,0,
0,0,5, 0,4,0, 8,0,0,
0,4,0, 7,0,2, 0,9,0,
0,0,8, 0,1,0, 7,0,0,
0,0,1, 2,0,5, 0,0,3,
0,6,0, 0,7,0, 0,8,0,
2,0,0, 0,0,0, 4,0,0,
};
// 問題のダンプ
printf( "data = " );
dumpData( data );
// クリアするまでチェックを繰り返す
int target = 0;
while( ! isCorrect( data ) ){
int subX = target % SUB_SIZE;
int subY = target / SUB_SIZE;
checkSubBlockAt( data, subX, subY );
target++;
if( target >= SUB_SIZE*SUB_SIZE){
target = 0;
}
}
// 結果のダンプ
printf( "result = " );
dumpData( data );
}
下記、実行結果です。
data = {
0 0 6 0 0 0 0 0 1
0 7 0 0 6 0 0 5 0
8 0 0 1 0 3 2 0 0
0 0 5 0 4 0 8 0 0
0 4 0 7 0 2 0 9 0
0 0 8 0 1 0 7 0 0
0 0 1 2 0 5 0 0 3
0 6 0 0 7 0 0 8 0
2 0 0 0 0 0 4 0 0
}
result = {
5 3 6 8 2 7 9 4 1
1 7 2 9 6 4 3 5 8
8 9 4 1 5 3 2 6 7
7 1 5 3 4 9 8 2 6
6 4 3 7 8 2 1 9 5
9 2 8 5 1 6 7 3 4
4 8 1 2 9 5 6 7 3
3 6 9 4 7 1 5 8 2
2 5 7 6 3 8 4 1 9
}
エラー判定を何もしていないので、解けないデータを入力すると無限ループに陥ると思います。
お気をつけください。