当前位置: 首页 > 工具软件 > Sudoku > 使用案例 >

Sudoku-Java

祁嘉木
2023-12-01

问题描述:数独(Sudoku)是一款大众喜爱的数字逻辑游戏。玩家需要根据9X9盘面上的已知数字,推算出所有剩余空格的数字,并且满足每一行、每一列、每一个粗线宫内的数字均含1-9,并且不重复。
输入:
包含已知数字的9X9盘面数组[空缺位以数字0表示]
输出:
完整的9X9盘面数组

输入描述:

包含已知数字的9X9盘面数组[空缺位以数字0表示]

输出描述:

完整的9X9盘面数组

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
bool isValid(const vector<vector<int>> &board,int x ,int y);
bool DFS(vector<vector<int>> &board)
{
   //遍历棋盘的每个位置
   for(int i=0;i<9;++i)
       for(int j=0;j<9;j++)
       {
           if(board[i][j]==0)
           {
               for(int k =0;k<9;k++)
               {
                   board[i][j] = 1+k;
                   if(isValid(board,i,j)&&DFS(board))
                       return true;
                   board[i][j] = 0;
               }
               return false;      
        }           
   }
   return true;     
}
 
bool isValid(const vector<vector<int>> &board,int x ,int y)
{
    int i,j;
    for(i=0;i<9;++i)
        if(i!=x&&board[i][y]==board[x][y])
        return false;
    for(j=0;j<9;++j)
        if(j!=y&&board[x][j]==board[x][y])
            return false;
     for(i=3*(x/3);i<3*(x/3+1);i++)
        for(j=3*(y/3);j<3*(y/3+1);j++)
            if((i!=x||j!=y)&&board[i][j]==board[x][y])
                return false;
     return true;
}
 
void Print(vector<vector<int>> board)
{
     for (int i = 0; i < 9; i++)
     {
        for (int j = 0; j < 8; j++)
            cout << board[i][j] <<' ';
        cout << board[i][8];
        cout << endl;
    }   
}
int main()
{
    //9宫格总共81个数字
    vector<vector<int>> board(9,vector<int>(9,0));
    int data;
    for(int i=0;i<9;i++)
        for(int j=0;j<9;j++)
        {
            cin >> data;
            board[i][j] =data;
        }
    DFS(board);
    Print(board); 
    board.clear(); 
}

 类似资料: