『数独』を解いてみようじゃないか！
こんな記事があった。
解けたら天才！ フィンランドの数学者が作った「世界一難しい数独」
＜※回答のヒントがあるので見たくない人はパスして…※＞
問題は、これ…。
----------------------
| 0 0 5 | 3 0 0 | 0 0 0 |
| 8 0 0 | 0 0 0 | 0 2 0 |
| 0 7 0 | 0 1 0 | 5 0 0 |
----------------------
| 4 0 0 | 0 0 5 | 3 0 0 |
| 0 1 0 | 0 7 0 | 0 0 6 |
| 0 0 3 | 2 0 0 | 0 8 0 |
----------------------
| 0 6 0 | 5 0 0 | 0 0 9 |
| 0 0 4 | 0 0 0 | 0 3 0 |
| 0 0 0 | 0 0 9 | 7 0 0 |
----------------------
じゃあ、解いてみようじゃないか！
…
…
…
結構難問。（汗）
とにかく適当に数字を入れて解いて行くしかない…。
…
…
…
何となく飽きたので止めた。（笑）
でも、解けないと何となく負けた気がする…。
…
一応、プログラマーだし…。
数独を解くプログラムでも作ってみようか♪
って、作ってみた…。
何だかんだで３時間ぐらい。
最初の考え方に間違いがあったし…。（汗）
多分頭が良い人ならもっと簡単に作るだろう。
そっからさらに色々ブラッシュアップしてみたけど…。
試しに２種類の処理を作って実行してみたら結果が違った。
結果１の上３段
----------------------
| 1 2 5 | 3 4 6 | 8 9 7 |
| 8 3 1 | 4 6 7 | 9 2 5 |
| 2 7 6 | 9 1 8 | 5 4 3 |
----------------------
結果２の上３段
----------------------
| 1 9 5 | 3 4 2 | 8 6 7 |
| 8 4 6 | 1 3 7 | 9 2 5 |
| 6 7 2 | 4 1 8 | 5 9 3 |
----------------------
コンだけ有れば多分解けるんじゃないの？
一個一個確認するのでも面倒なので
１だけ重複しないのを確認してから
エクセルで左右上下の和を取ってみる。
全ての方向で４５になるので成立しているのは、間違い無い！
所で…
数独って複数の回答を持っているのは、有り？
どうなんでしょう？
ちなみにこのプログラム数独の開発や確認に使えるかも？（笑）
兎も角、数独で悩まされたらこれにかけて即効で解こう！
…
それじゃあ駄目だろう…。
※『Microsoft Visual Studio 6.0』で開発だよ。
数独.cpp -------------------------------
//******************************************************************************
// 『数独』を解くプログラム
//
// １．左上から右側へ空きブロックを検索する。右に行き着くと一段下の左に移動する。
// ２．空きブロックに「入れられる数」を入れる。
// ３．ブロックを埋められなければ一つ戻り番号を一上げて再開
// ４．空きブロックが埋まったら終了
//******************************************************************************
//**************************************
// include
//**************************************
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <memory.h>
//**************************************
// define
//**************************************
#define original_data \
0, 0, 5, 3, 0, 0, 0, 0, 0, \
8, 0, 0, 0, 0, 0, 0, 2, 0, \
0, 7, 0, 0, 1, 0, 5, 0, 0, \
4, 0, 0, 0, 0, 5, 3, 0, 0, \
0, 1, 0, 0, 7, 0, 0, 0, 6, \
0, 0, 3, 2, 0, 0, 0, 8, 0, \
0, 6, 0, 5, 0, 0, 0, 0, 9, \
0, 0, 4, 0, 0, 0, 0, 3, 0, \
0, 0, 0, 0, 0, 9, 7, 0, 0,
//**************************************
// work
//**************************************
int block_data[9][9] =
{
original_data
};
int block_orignal[9][9] =
{
original_data
};
int counter = 0;
//**************************************
// ブロックに入れられる数かチェックします。
// Ｔ＝入れられる数値
//**************************************
bool check_value( int xp, int yp, int value )
{
int x, y;
int table[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, };
for( x = 0 ; x < 9 ; x++)
table[ block_data[yp][x ] ] = 0;
for( y = 0 ; y < 9 ; y++)
table[ block_data[y ][xp] ] = 0;
return table[value] != 0;
}
//**************************************
// 次の場所を求める。
//**************************************
bool point_next_add( int xp, int yp, int &xnp, int &ynp )
{
xnp = xp;
ynp = yp;
if( ++xnp < 9 )
return true;
xnp = 0;
if( ++ynp < 9 )
return true;
return false;
}
//**************************************
// 次の場所を求める。
//**************************************
bool point_next_dec( int xp, int yp, int &xnp, int &ynp )
{
xnp = xp;
ynp = yp;
if( --xnp >= 0 )
return true;
xnp = 8;
if( --ynp >= 0 )
return true;
return false;
}
//**************************************
// 画面へ結果の出力
//**************************************
void block_print( int xp, int yp )
{
int x, y;
system( "cls" );
printf( "%d - %d : %4d\n" , xp, yp, counter++ );
for( y = 0 ; y < 9 ; y++)
{
if( ( y % 3 ) == 0 )
printf( "-------------------------------\n" );
for( x = 0 ; x < 9 ; x++)
{
if( ( x % 3 ) == 0 )
printf( "|" );
printf( " %d ", block_data[y][x] );
}
printf( "| \n" );
}
printf( "-------------------------------\n" );
}
//**************************************
// ファイルへ結果の出力
//**************************************
void block_save( FILE *file )
{
int x, y;
char time_string[128];
_strtime( time_string );
fprintf( file, "%s - %4d\n", time_string, counter++ );
for( y = 0 ; y < 9 ; y++)
{
if( ( y % 3 ) == 0 )
fprintf( file, "-------------------------------\n" );
for( x = 0 ; x < 9 ; x++)
{
if( ( x % 3 ) == 0 )
fprintf( file, "|" );
fprintf( file, " %d ", block_data[y][x] );
}
fprintf( file, "| \n" );
}
fprintf( file, "-------------------------------\n" );
}
//**************************************
// 探索処理
//**************************************
int sudoku_check( int xp, int yp, bool point_next( int, int, int&, int& ) )
{
int data, xnp, ynp, next_flag;
int number = 1;
block_print( xp, yp );
if( block_data[yp][xp] != 0 )
{// 初期値があるので次へ
if( !point_next( xp, yp, xnp, ynp ) )
return -1; // 終了
if( ( data = sudoku_check( xnp, ynp, point_next ) ) < 0 )
return -1;
return 0;
}
// 初期値が無いので戻る時には、０に戻す。
next_flag = !point_next( xp, yp, xnp, ynp );
for( number = 1 ; number <= 9 ; number++ )
{
if( !check_value( xp, yp, number ) )
continue;
block_data[yp][xp] = number;
if( next_flag )
return -1;
if( ( data = sudoku_check( xnp, ynp, point_next ) ) < 0 )
return -1;
}
block_data[yp][xp] = 0;
return 0;
}
//**************************************
// メイン
//**************************************
void main( void )
{
FILE *file;
file = fopen( "sudoku.log", "w" );
block_save( file );
// ０ｘ０からチェック
counter = 1;
sudoku_check( 0, 0, &point_next_add );
block_print( 0, 0 );
block_save( file );
memcpy( block_data, block_orignal, sizeof( block_data ) );
// ８ｘ８からチェック
counter = 1;
sudoku_check( 8, 8, &point_next_dec );
block_print( 8, 8 );
block_save( file );
fclose( file );
}
//******************************************************************************
// end
//******************************************************************************
| 固定リンク
コメント