« 『サンパーク武蔵境駅高架下自転車等駐車場』を使ってみる。 | トップページ | PCが起動しないよぉ~!?(泣) »

2010年8月30日 (月)

『数独』を解いてみようじゃないか!

こんな記事があった。

解けたら天才! フィンランドの数学者が作った「世界一難しい数独」

<※回答のヒントがあるので見たくない人はパスして…※>

問題は、これ…。

----------------------
| 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 |
----------------------

じゃあ、解いてみようじゃないか!

結構難問。(汗)

とにかく適当に数字を入れて解いて行くしかない…。

何となく飽きたので止めた。(笑)

でも、解けないと何となく負けた気がする…。

一応、プログラマーだし…。

数独を解くプログラムでも作ってみようか♪

って、作ってみた…。

何だかんだで3時間ぐらい。

最初の考え方に間違いがあったし…。(汗)

多分頭が良い人ならもっと簡単に作るだろう。

そっからさらに色々ブラッシュアップしてみたけど…。

試しに2種類の処理を作って実行してみたら結果が違った。

結果1の上3段
----------------------
| 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 |
----------------------

結果2の上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 |
----------------------

コンだけ有れば多分解けるんじゃないの?

一個一個確認するのでも面倒なので
1だけ重複しないのを確認してから
エクセルで左右上下の和を取ってみる。
全ての方向で45になるので成立しているのは、間違い無い!

所で…

数独って複数の回答を持っているのは、有り?

どうなんでしょう?

ちなみにこのプログラム数独の開発や確認に使えるかも?(笑)

兎も角、数独で悩まされたらこれにかけて即効で解こう!

それじゃあ駄目だろう…。

※『Microsoft Visual Studio 6.0』で開発だよ。

数独.cpp -------------------------------

//******************************************************************************
//    『数独』を解くプログラム
//   
//    1.左上から右側へ空きブロックを検索する。右に行き着くと一段下の左に移動する。
//    2.空きブロックに「入れられる数」を入れる。
//    3.ブロックを埋められなければ一つ戻り番号を一上げて再開
//    4.空きブロックが埋まったら終了
//******************************************************************************
//**************************************
//    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;
//**************************************
//    ブロックに入れられる数かチェックします。
//    T=入れられる数値
//**************************************
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;
    }

    // 初期値が無いので戻る時には、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 );

    // 0x0からチェック
    counter    = 1;
    sudoku_check( 0, 0, &point_next_add );
    block_print( 0, 0 );
    block_save( file );

    memcpy( block_data, block_orignal, sizeof( block_data ) );

    // 8x8からチェック
    counter    = 1;
    sudoku_check( 8, 8, &point_next_dec );
    block_print( 8, 8 );
    block_save( file );

    fclose( file );
}
//******************************************************************************
//    end
//******************************************************************************

|

« 『サンパーク武蔵境駅高架下自転車等駐車場』を使ってみる。 | トップページ | PCが起動しないよぉ~!?(泣) »

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/108365/49290642

この記事へのトラックバック一覧です: 『数独』を解いてみようじゃないか!:

« 『サンパーク武蔵境駅高架下自転車等駐車場』を使ってみる。 | トップページ | PCが起動しないよぉ~!?(泣) »