【問題】請問數獨的c++怎麼寫

[快刀亂麻 10]

我找到了原始碼 跑出來是1*9的 可是有瑕疵 就是把數字改掉就會有重複的可能(假如我把第4個數字改成3 那跑出來就會有兩個3了) 請會的人幫忙改一下 或提供自己的寫法也可以

如果有跑出來是9*9的更佳

謝謝

對了 補充問題一下 數獨就是每一行每一列的數字都是1~9(所以每一列或每一行加起來會等於45) 而且不能重複

#include <stdio.h>

#include <stdlib.h>

int main()

{

int sdk[9]={0,0,4,0,0,8,0,2,5};

int j,k,n;

for(j=0,k=1;j<9;j++)

if(sdk[j]==0){ //找0

for(n=0;n<9;n++)

if(sdk[n]==k)

{

k++;

}

sdk[j] = k;

}

for(j=0;j<9;j++)

printf("%d ",sdk[j]);

system("pause");

}

[TerryW 10]

這跟人腦玩數獨是差不多的

你可以先統計每個空格可能的數字是哪些

然後找出只有一個可能數字的空格，將其數字填入後

從同行同列同九宮格的空格的可能數字中刪除該數字

如此不斷進行下去

若找不到只有一個可能數字的空格，就先猜個數字填入看看結果，然後進行上述步驟，若不行就從頭來過

[電腦狂 10]

數獨喔...

其實用AI開發的Programming Language會寫得很開心...

因為code超短@@

ex : prolog

[PsTEm 10]

對了 補充問題一下 數獨就是每一行每一列的數字都是1~9(所以每一列或每一行加起來會等於45) 而且不能重複

恩..

這個演算法好像有問題

如果整盤的數字都是5

好像也會通過

我看過的作法是宣告陣列

紀錄哪些數字出現過

然後一行一行觀察

[電腦狂 10]

恩..

這個演算法好像有問題

如果整盤的數字都是5

好像也會通過

我看過的作法是宣告陣列

紀錄哪些數字出現過

然後一行一行觀察

他的意思是每一行每一列都必須是1~9不能重複

這演算法基本上沒問題

和你的作法概念上是相同的

話說數獨簡易版（好像是5*5，有點忘了）

是96年（還是95忘了= ="）奧林匹亞初選題目唷

[PsTEm 10]

1樓的程式修好了

#include <stdio.h>

#include <stdlib.h>

int main()

{

int sdk[9]={0,0,9,0,0,8,0,2,5};

int j,k,n;

for(j=0,k=1;j<9;j++)

if(sdk[j]==0){ //找0

for(n=0;n<9;n++)

if(sdk[n]==k){

k++;

n=0;//重新偵測碰撞

}

sdk[j] = k;

}

for(j=0;j<9;j++)

printf("%d ",sdk[j]);

system("pause");

}

他是用偵測目前想填的k值是否會發生碰撞

如果進入二維的話

這種方法好像會出問題(這個方法應該市直接填答案,錯了在嚓掉)

然後我說的問題

是

(所以每一列或每一行加起來會等於45)

不過

我想到的方法是

9*9的棋盤

9*9*9的'可能性棋盤'//記載可能答案

整個程式是

讀取棋盤

填寫'可能性棋盤'

L1:

搜尋只有一個可能數字的點

填入數字

修改該行 該列 該方塊 的可能性棋盤

如果棋盤還沒填完且無任何只有一個可能數字的點--->雙答案

如果棋盤填完 跳出迴圈且輸出棋盤

GOTO L1

只是...整個程式感覺好麻煩="=

(其實我只是把我解數獨的方法打上來而已)

[foxs91092 10]

他的意思是每一行每一列都必須是1~9不能重複

這演算法基本上沒問題

和你的作法概念上是相同的

話說數獨簡易版（好像是5*5，有點忘了）

是96年（還是95忘了= ="）奧林匹亞初選題目唷

95奧賽初選 3

富翁種花 9*9，沒有簡化吧...

個人解過一題ACM的數獨

989 Su Doku

http://luckycat.kshs.kh.edu.tw/homework/q989.htm

程式碼提供參考 (Backtracing):$

#include <cstdlib>
#include <cstdio>
#define MAX 9
using namespace std;

bool cols[MAX][MAX];
bool rows[MAX][MAX];
//information

bool blocks[MAX][MAX];
//blocks information

int now_map[MAX][MAX];
//map information

struct blank{
       int b_row;
       int b_col;
       };

blank blanks[MAX*MAX];
//blank structure
int sudoku(int);

int block_j(int, int, int);


int N;
//len of block
int remaining;
bool solved;
bool no_solve;

int main(int argc, char *argv[])
{
    bool P=false;

    while(scanf("%d", &N)!=EOF)
    {

    if(P)
    putchar('\n');

    P=true;


    if(N!=1)
    {

        remaining=0;
        solved=false;
        no_solve=false;

        for(int i=0; i<N*N; i++)
        for(int j=0; j<N*N; j++)
        cols[i][j]=false;

        for(int i=0; i<N*N; i++)
        for(int j=0; j<N*N; j++)
        rows[i][j]=false;

        for(int i=0; i<N*N; i++)
        for(int j=0; j<N*N; j++)
        blocks[i][j]=false;

        //initialization

        for(int i=0; i<N*N; i++)
        for(int j=0; j<N*N; j++)
        {
        scanf("%d", &now_map[i][j]);  

        if(now_map[i][j]==0)
        {
        blanks[remaining].b_row=i;
        blanks[remaining].b_col=j;                    
        remaining++;
        }
        else if(!no_solve)
        {
        int B=block_j(i, j, N); 

        if(!rows[i][now_map[i][j]-1]&&!cols[j][now_map[i][j]-1]&&!blocks[B][now_map[i][j]-1])
        {        
        rows[i][now_map[i][j]-1]=true;
        cols[j][now_map[i][j]-1]=true;

        blocks[B][now_map[i][j]-1]=true;
        }
        else
        {
        no_solve=true;
        }

        }

        }
        //load map

        if(!no_solve)
        sudoku(remaining);
        //backtracing

        if(!solved||no_solve)
        printf("NO SOLUTION\n");
    }
    else
    {
    int temp;
    scanf("%d", &temp);
    printf("1\n");
    }
                      }
    //process
    return 0;
}

int sudoku(int remain)
{

    if(solved)
    {
    return 0;
}
    if(remain==0)
    {

    for(int i=0; i<N*N; i++)
    {
    printf("%d", now_map[i][0]);

    for(int j=1; j<N*N; j++)
    printf(" %d", now_map[i][j]);

    putchar('\n');

}
    solved=true;

    return 0;
                 }
    //solved

        for(int k=0; k<N*N&&!solved; k++)
        {
        int B=block_j(blanks[remaining-remain].b_row, blanks[remaining-remain].b_col, N);    

        if(!rows[blanks[remaining-remain].b_row][k]&&!cols[blanks[remaining-remain].b_col][k]&&!blocks[B][k])
        {        
        rows[blanks[remaining-remain].b_row][k]=true;
        cols[blanks[remaining-remain].b_col][k]=true;
        blocks[B][k]=true;
        now_map[blanks[remaining-remain].b_row][blanks[remaining-remain].b_col]=k+1;

        sudoku(remain-1);

        rows[blanks[remaining-remain].b_row][k]=false;
        cols[blanks[remaining-remain].b_col][k]=false;
        blocks[B][k]=false;
        now_map[blanks[remaining-remain].b_row][blanks[remaining-remain].b_col]=0;
        }

                }


        //backtracing
}

int block_j(int row, int col, int len)
{

    int block;

    block=((row/len)*len)+col/len;

    return block;

}