WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
C语言 实现数独游戏
C语言 实现数独游戏

实现技术

  1. 使用_kbhit()函数与_getch()函数从键盘实时获得输入
int keyboardInput(){
if (_kbhit()) return _getch();
return -1;
}
  1. 使用具柄与SetConsoleCursorPosition函数设置光标的位置用来更新界面
void screenMoveTo(int x, int y){
COORD pos;
HANDLE hOutput;
pos.X = x, pos.Y = y;
hOutput = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleCursorPosition(hOutput, pos);
}
  1. 使用SetConsoleTextAttribute函数来对输出内容设置指定颜色
void printColor(char c, int color){
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | color);
printf("%c", c);
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
}
  1. 生成保证有解的数独问题

有一种简单的方法就是随机对每个位置填放数字、然后在把一些位置设置为未填写,然后检查这个数独是否有借,如果有解则生成成功,否则重新生成。

这种生成方式非常简单,但是成功的可能性很低。想要能够成功生成,需要花费\infty的时间emmmm

我们可以使用一种动态生成数独的方法,可以知道一个既定事实,那就是当空格非常多的时候我们随机摆放一堆数字令其依旧是一个可行的数独的可能性是大的,而当空格比较少的时候,我们任意摆放一个数字都有可能造成数独无解。所以我们使用一种动态生成数独的方法,通过进行若干轮填充数字来完成数独问题的构造,每一轮,我们向数独中投入随机投入待插入数字数量/4的数字,使用DFS检查一下是否有解,如果有解则进行下一轮填充,否则回滚本次操作,重新进行本轮。

效果预览

  1. 开始界面
    https://blog.wnjxyk.cn/wp-content/uploads/2018/11/%E5%B1%8F%E5%B9%95%E5%BF%AB%E7%85%A7-2018-11-28-%E4%B8%8A%E5%8D%889.17.23.png
  2. 帮助界面
    https://blog.wnjxyk.cn/wp-content/uploads/2018/11/%E5%B1%8F%E5%B9%95%E5%BF%AB%E7%85%A7-2018-11-28-%E4%B8%8A%E5%8D%889.17.32.png
  3. 生成数独界面
    https://blog.wnjxyk.cn/wp-content/uploads/2018/11/%E5%B1%8F%E5%B9%95%E5%BF%AB%E7%85%A7-2018-11-28-%E4%B8%8A%E5%8D%889.17.40.png
  4. 游戏界面
    https://blog.wnjxyk.cn/wp-content/uploads/2018/11/%E5%B1%8F%E5%B9%95%E5%BF%AB%E7%85%A7-2018-11-28-%E4%B8%8B%E5%8D%8812.55.15.png

代码

#include <stdio.h>
#include <string.h>
#include <Windows.h>
#include <time.h>
#include <conio.h>

// Game
#define MAXN 9
#define LEVEL 30
#define RANDOM_LIMIT 30
// Display
#define DISPLAYX 6
#define DISPLAYY 1
// Clock
#define SLEEP_TIME 50
#define bREFRESH 50
#define bCLOCKTICK 5
// Game State
#define nSTATE_WELCOME 0
#define nSTATE_RUNNING 1
#define nSTATE_WIN 2
#define nSTATE_HELP 3

void printSudoku(int sudoku[][MAXN], int fixedFlag[][MAXN], int nX, int nY);

// Get Keyboard Input
int keyboardInput(){
if (_kbhit()) return _getch();
return -1;
}

// Print Adgjust
void screenMoveTo(int x, int y){
COORD pos;
HANDLE hOutput;
pos.X = x, pos.Y = y;
hOutput = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleCursorPosition(hOutput, pos);
}

// Print Sudoku For Debuging
void debugSudoku(int sudoku[][MAXN]){
int i, j;
for (i=0; i<MAXN; i++){
for (j=0; j<MAXN; j++){
printf("%d", sudoku[i][j]);
}
printf("\n");
}
}

// Check Sudoku is legal till now
int checkSudoku(int sudoku[][MAXN]){
int i, j, p, q, vis[10];
for (i=0; i<MAXN; i++){
memset(vis, 0, sizeof(vis));
for (j=0; j<MAXN; j++){
if (sudoku[i][j]==0) continue;
if (vis[sudoku[i][j]]==0) vis[sudoku[i][j]]=1; else return 0;
}
}
for (j=0; j<MAXN; j++){
memset(vis, 0, sizeof(vis));
for (i=0; i<MAXN; i++){
if (sudoku[i][j]==0) continue;
if (vis[sudoku[i][j]]==0) vis[sudoku[i][j]]=1; else return 0;
}
}
for (i=0; i<MAXN; i+=MAXN/3) for (j=0; j<MAXN; j+=MAXN/3){
memset(vis, 0, sizeof(vis));
for (p=0; p<MAXN/3; p++) for (q=0; q<MAXN/3; q++){
if (sudoku[i+p][j+q]==0) continue;
if (vis[sudoku[i+p][j+q]]==0) vis[sudoku[i+p][j+q]]=1; else return 0;
}
}
return 1;
}

// Count finished Numbers
int countSudoku(int sudoku[][MAXN]){
int i, j, ret=0;
for (i=0; i<MAXN; i++){
for (j=0; j<MAXN; j++){
if (sudoku[i][j]!=0) ++ret;
}
}
return ret;
}

// Dfs for Answers of Sudoku
int dfsSudoku(int sudoku[][MAXN], int idx){
if (idx==MAXN*MAXN) return 1;
int x=idx/MAXN, y=idx%MAXN, c;
if (sudoku[x][y]) return dfsSudoku(sudoku, idx+1);
for (c=1; c<=MAXN; c++){
sudoku[x][y]=c;
if (!checkSudoku(sudoku)) {
sudoku[x][y]=0;
continue;
}
if (dfsSudoku(sudoku, idx+1)) return 1; else sudoku[x][y]=0;
}
return 0;
}

// Try to find a solution for sodoku
int solveSudoku(int sudoku[][MAXN]){
static int ssudoku[MAXN][MAXN];
int i, j;
for (i=0; i<MAXN; i++) for (j=0; j<MAXN; j++) ssudoku[i][j]=sudoku[i][j];
if (checkSudoku(ssudoku)==0) return 0;
return dfsSudoku(ssudoku, 0);
}

// Generate a sudoku problem with available solutions
void generateSudoKu(int sudoku[][MAXN], int fixedFlag[][MAXN]){
int i, j, rt, lim=MAXN*MAXN-LEVEL-rand()%6;
static int rollback[MAXN*MAXN];
for (i=0; i<MAXN; i++) for (j=0; j<MAXN; j++) fixedFlag[i][j]=sudoku[i][j]=0;
for (rt=0; rt<lim;){
int step, top=0;
if (rt==0) step=max(1, (lim-rt)/4); else step=max(1, (lim-rt)/8);
// Random
for (i=0; i<step; i++){
int x=rand()%MAXN, y=rand()%MAXN;
while(sudoku[x][y]) x=rand()%MAXN, y=rand()%MAXN;
sudoku[x][y]=rand()%MAXN+1;
if (checkSudoku(sudoku)==0) sudoku[x][y]=0, --i; else{
rollback[top++]=x*MAXN+y;
}
}

// Check or maybe rollback
printSudoku(sudoku, fixedFlag, 10, 10);
if (solveSudoku(sudoku)==0){
for (i=0; i<top; i++){
int x=rollback[i]/MAXN, y=rollback[i]%MAXN;
sudoku[x][y]=0;
}
}else{
rt+=step;
screenMoveTo(9+DISPLAYX, 1+DISPLAYY), printf("%2d", (int)(100*rt/lim));
printSudoku(sudoku, fixedFlag, 10, 10);
}
}
for (i=0; i<MAXN; i++) for (j=0; j<MAXN; j++) fixedFlag[i][j]=(sudoku[i][j]?1:0);
}

// Calculate Screen Position for sudoku
int getGridX(int x){ return x+(x/3+1); }
int getGridY(int y){ return y+(y/3+1)+2; }

// Print the Grid of Game
void printGrid(){
int i, j;
for (i=0; i<13; i++){
screenMoveTo(0+DISPLAYX, i+2+DISPLAYY);
for (j=0; j<13; j++) printf("#");
}
for (i=0; i<MAXN; i++) for (j=0; j<MAXN; j++) screenMoveTo(getGridX(i)+DISPLAYX, getGridY(j)+DISPLAYY), printf("?");
screenMoveTo(3+DISPLAYX, 0+DISPLAYY); printColor('*', FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE); printf("Sudoku");
}

// Color Print
void printColor(char c, int color){
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | color);
printf("%c", c);
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
}
void printfColor(char c[], int color){
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | color);
int i; for(i=0; c[i]; i++) printf("%c", c[i]);
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
}

// Print Sudoku inside the Game Grid
void printSudoku(int sudoku[][MAXN], int fixedFlag[][MAXN], int nX, int nY){
int i, j, c, col;
for (i=0; i<MAXN; i++){
for (j=0; j<MAXN; j++){
screenMoveTo(getGridX(i)+DISPLAYX, getGridY(j)+DISPLAYY);
c=(sudoku[i][j]==0?'?':'0'+sudoku[i][j]);
if (fixedFlag[i][j]) col=FOREGROUND_GREEN; else col=FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE;
if (i==nY && j==nX) col=FOREGROUND_RED;
printColor(c, col);
}
}
}

// Init SudokuGame
void initSudoku(int sudoku[][MAXN], int fixedFlag[][MAXN]){
screenMoveTo(-2+DISPLAYX, 1+DISPLAYY), printf("Generating[ 0/100]");
generateSudoKu(sudoku, fixedFlag);
screenMoveTo(0, 1+DISPLAYY), printf(" ");
}

int main(){
srand((unsigned)time(NULL));
static int nState, nTime, nX, nY, sudoku[MAXN][MAXN], fixedFlag[MAXN][MAXN];
printGrid(), nState = nSTATE_WELCOME;
int refresh=0, clockTick=0;
while(1){
// Keyboard Input Control
char keyInput=keyboardInput();
if (keyInput!=-1){
switch(nState){
case nSTATE_WELCOME:
if (keyInput=='s') {
screenMoveTo(0, DISPLAYY+15), printf(" ");
initSudoku(sudoku, fixedFlag);
nState=nSTATE_RUNNING;
nX=nY=nTime=0;
}
if (keyInput=='h') nState=nSTATE_HELP;
break;
case nSTATE_RUNNING:
switch(keyInput){
case 'w':
if (nX>0) --nX;
break;
case 'a':
if (nY>0) --nY;
break;
case 's':
if (nX+1<MAXN) ++nX;
break;
case 'd':
if (nY+1<MAXN) ++nY;
break;
default:
if ('0'<=keyInput && keyInput<='9' && fixedFlag[nY][nX]==0){
sudoku[nY][nX]=keyInput-'0';
if (countSudoku(sudoku)==MAXN*MAXN){
screenMoveTo(DISPLAYX+0, DISPLAYY+15);
if (checkSudoku(sudoku)) nState=nSTATE_WIN; else{
printfColor("Wrong Answer!", FOREGROUND_RED);
}
}else screenMoveTo(DISPLAYX+0, DISPLAYY+15), printf(" ");
}
}
break;
case nSTATE_HELP:
case nSTATE_WIN:
if (keyInput == 'r') {
nState=nSTATE_WELCOME;
screenMoveTo(0, DISPLAYY+15), printf(" ");
screenMoveTo(0, DISPLAYY+16), printf(" ");
screenMoveTo(0, DISPLAYY+17), printf(" ");
screenMoveTo(0, DISPLAYY+18), printf(" ");
}
break;

}
refresh=0;
}

// One Second Interruptre
if (clockTick<=0){
++nTime;
if (nState==nSTATE_RUNNING) refresh=0;
clockTick=bCLOCKTICK;
}

// Repaint Interrupter
if (refresh<=0){
switch(nState){
case nSTATE_WELCOME:
screenMoveTo(-2+DISPLAYX, 1+DISPLAYY), printf(" Press s to Start. ");
screenMoveTo(DISPLAYX-2, DISPLAYY+15), printfColor("Press h For Help", FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
break;
case nSTATE_RUNNING:
printSudoku(sudoku, fixedFlag, nX, (nTime&1)*9+nY);
screenMoveTo(0+DISPLAYX, 1+DISPLAYY), printf(" Time:%2dM%2dS ", nTime/4/60, nTime/4%60);
break;
case nSTATE_WIN:
printSudoku(sudoku, fixedFlag, 10, 10);
screenMoveTo(DISPLAYX+0, DISPLAYY+15), printf(" ");
screenMoveTo(DISPLAYX+3, DISPLAYY+15), printfColor("You Win!", FOREGROUND_GREEN);
screenMoveTo(DISPLAYX-5, DISPLAYY+16), printf("Press r Return to Welcome.");
break;
case nSTATE_HELP:
screenMoveTo(-2+DISPLAYX, 1+DISPLAYY), printf(" Help ");
screenMoveTo(DISPLAYX-5, DISPLAYY+15), printf("Press r Return to Welcome.");
screenMoveTo(DISPLAYX-3, DISPLAYY+16), printf("Press WASD to Move,");
screenMoveTo(DISPLAYX-5, DISPLAYY+17), printf("Press 1-9 to Set Number,");
screenMoveTo(DISPLAYX-3, DISPLAYY+18), printf("Press 0 to Cancel.");
}
refresh=bREFRESH;
}

--refresh, --clockTick;
screenMoveTo(0, 0); //printf("%d %d %c ", refresh, clockTick, keyInput);
Sleep(SLEEP_TIME);
}
return 0;
}
赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

发表评论

textsms
account_circle
email

WNJXYKのBlog

C语言 实现数独游戏
实现技术 使用_kbhit()函数与_getch()函数从键盘实时获得输入 int keyboardInput(){ if (_kbhit()) return _getch(); return -1; } 使用具柄与SetConsoleCursorPosition函数设置光…
扫描二维码继续阅读
2018-11-28
<--! http2https -->