Leetcode37题，解数独

xiaoxiao2023-11-09 143

leetcode 37题，自动解数独

老婆听说我在研究自动解数独，赞叹地说这是不是人工智能啊。咳咳，脸红中，其实没那么玄乎，就是一道算法题，只不过其题材是大家喜闻乐见的数独而已。 2013年时，那时还在工行，刚海外调回来，工作上比较空，且那时候有个大新闻，一个中国农民解出了“史上最难数独”，我也跃跃欲试。于是鼓捣了一个工作日，用C写了一个算法出来，自测通过并发表到内部技术论坛上。为啥不用熟悉的Java？那时工作机性能不行，打开一个当前要维护的银行Java项目已经有不流畅的感觉，我实在不想再开一个Java IDE进程，用记事本写Java又不太习惯。后来是用C在UltraEdit里面写好并用gcc编译的。

leetcode 37题也是数独题目解出来后是如下：

解题思路

数独的解题思路有两种：

一种是正向递推的“消元法”

模拟人脑解数独的方法，就是统计每个单元格横向,竖向,宫格这三个维度中其他数字，并将本单元格[1-9]这9种可能性减去其他数字，剩下如果只有一个数字，那就是本单元格确定的数字，这种方法不需要回溯，但是只能应对简单级别的数独题目。这种方法下的测试案例

[["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]

另一种是反向解题的“递归法”

从map取一个待定的点，遍历其set范围，当某值时，设置board，删map，然后递归下一步，发现不行要回退。注意这里的关键是“回退”，就是上一个单元格尝试性地定个值（可能后来发现不合适，这个值会被推翻），这个单元格在此基础上继续尝试，如果哪一步发现尝试不下去了，就回退掉该单元格取值。这种方法下的测试案例

[[".",".","9","7","4","8",".",".","."],["7",".",".",".",".",".",".",".","."],[".","2",".","1",".","9",".",".","."],[".",".","7",".",".",".","2","4","."],[".","6","4",".","1",".","5","9","."],[".","9","8",".",".",".","3",".","."],[".",".",".","8",".","3",".","2","."],[".",".",".",".",".",".",".",".","6"],[".",".",".","2","7","5","9",".","."]]

消元法解决数独问题的Java代码

package com.zzz.life; import java.util.*; public class Sudo { class Point { int i; //二维数组下标 int j; //二维数组下标 int id; //所在方格id，比如11区 Point(int i, int j) { this.i = i; this.j = j; this.id = (i<3?1:(i<6?2:3))*10 + (j<3?1:(j<6?2:3)); } @Override public boolean equals(Object obj) { return obj instanceof Point && (this.i==((Point)obj).i && this.j==((Point)obj).j); } @Override public int hashCode() { return (i+j+id)%1024; } } private static final int SIZE = 9; private Set<Character> cloneSet() { final char[] possibility = new char[]{'1','2','3','4','5','6','7','8','9'}; Set<Character> ret = new HashSet<>(); for (char i : possibility) { ret.add(i); } return ret; } private void setInit(char[][] board, Map<Point, Set<Character>> map, Queue<Point> q) { map.clear(); q.clear(); for (int i=0; i<SIZE; i++) { for (int j=0; j<SIZE; j++) { Point tmp = new Point(i,j); if (board[i][j] == '.') { map.put(tmp, cloneSet()); } else { q.offer(tmp); } } } System.out.println(map.size() + "|" + q.size()); } private void demention(char[][] board, Map<Point, Set<Character>> map, Queue<Point> q) { Point tmp = q.poll(); if (map.containsKey(tmp)) map.remove(tmp); char posval = board[tmp.i][tmp.j]; for (Point point : map.keySet()) { if (point.i == tmp.i || point.j == tmp.j || point.id == tmp.id) { Set<Character> posset = map.get(point); posset.remove(posval); if (posset.size() == 1) { q.offer(point); char c = posset.iterator().next(); board[point.i][point.j] = c; } } } } private boolean check(char[][] board, Point point, char val) { for (int i=0; i<SIZE; i++) { for (int j=0; j<SIZE; j++) { Point tmp = new Point(i, j); if (tmp.i==point.i || tmp.j==point.j || tmp.id == point.id) { if (tmp.i == point.i && tmp.j == point.j) return true; if (board[tmp.i][tmp.j] == val) { System.out.println(tmp.i +"|"+tmp.j); return false; } } } } return true; } public boolean recusive(char[][] board, Map<Point, Set<Character>> map, Iterator<Point> iterator) { Point p = iterator.next(); System.out.println("not finished yet! ["+ p.i +"|"+ p.j + "]"); Set<Character> set = map.get(p); for (char c : set) { board[p.i][p.j] = c; if (check(board, p, c) && (iterator.hasNext() && recusive(board, map, iterator))) { return true; } else { board[p.i][p.j] = '.'; } } return false; } public void solveSudoku(char[][] board) { //思路：降维法，将用‘。’表示的不可能性，变为1-9的概率数组 //1.建立可能矩阵，已有条件进入降维队列 //2.利用降维队列中内容，循环减少可能矩阵的可能性 //3.期间发现size为1的，降维，该点进入降维队列，作为下一轮的弹药 //如此循环直到所有点都降维了 Map<Point, Set<Character>> map = new HashMap<>(); Queue<Point> q = new LinkedList<>(); setInit(board, map, q); //降维 while (!q.isEmpty()) { demention(board, map, q); } //后来发现需要猜，所以到最后如果可能矩阵还是有未降维的，则需要逐一尝试； //采用递归机制，从map取一个待定的点，遍历其set范围，当某值时，设置board，删map，然后递归下一步，发现不行要回退 //如果map中只有一个待定点了，遍历check就行了 while (map.size() > 0) { System.out.println("not finished yet! " + map.size()); Iterator<Point> iterator = map.keySet().iterator(); recusive(board, map, iterator); } } public static void main(String[] args) { char[][] board = new char[][]{ {'.','.','9','7','4','8','.','.','.'}, {'7','.','.','.','.','.','.','.','.'}, {'.','2','.','1','.','9','.','.','.'}, {'.','.','7','.','.','.','2','4','.'}, {'.','6','4','.','1','.','5','9','.'}, {'.','9','8','.','.','.','3','.','.'}, {'.','.','.','8','.','3','.','2','.'}, {'.','.','.','.','.','.','.','.','6'}, {'.','.','.','2','7','5','9','.','.'} }; Sudo solution = new Sudo(); solution.printBoard(board); solution.solveSudoku(board); solution.printBoard(board); } private void printBoard(char[][] board) { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { System.out.print(board[i][j] + " "); } System.out.println(); } } }

后来终于找到了我在2013年写的c的数独解法(递归法)

在leetcode上同样编译测试通过

#include <stdlib.h> #include <stdio.h> #include <time.h> #include <sys/timeb.h> int shudu[10][10]; //保存数独，使用时下标从1开始 int tt[10][10][10]; //保存数独可能取值，数独每点对应这里一组 FILE* flog; //日志文件 FILE* fshudu; //读取数独题目所在文件 //给数独数组的有值节点赋值 int init_shudu(void); //初始化数独数组对应的三维数组 int init_tt(int x, int y); //打印数独和记运行时间 void print_shudu(void); //数独求解函数，采用递归方式从上到下从左到右求解 int looper(int x, int y); //判断数独某单元格值没有重复性 int no_repeat(int x, int y, int value); int main(int argc, char* argv[]) { int i, j, ret; fopen_s(&flog, "mylog.txt","w"); printf("开始进行数独求解！----------------\n"); fprintf(flog, "开始进行数独求解！----------------\n"); ret = init_shudu(); if (ret != 0) goto Error; ret = init_tt(0, 0); if (ret != 0) goto Error; print_shudu(); ret = looper(1, 1); if (ret != 0) goto Error; print_shudu(); //对解出的数独进行逐格校验 for (i=1; i<=9; i++) for (j=1; j<=9; j++) if (no_repeat(i, j, shudu[i][j]) != 0) fprintf(flog, "检查发现单元[%d,%d]值不对！\n",i,j); printf("数独求解结束！----------------\n"); fprintf(flog, "数独求解结束！----------------\n"); fclose(flog); printf("请按回车键退出..."); getchar(); return 0; Error: fclose(flog); printf("程序发生异常终止！请检查日志！\n"); printf("请按回车键退出..."); getchar(); return ret; } /**初始化数独数组(9*9 矩阵)有值单元格,无值则为0 */ int init_shudu(void) { int i, j, num, cnt = 0; for(i=1; i<=9; i++) for(j=1; j<=9; j++) shudu[i][j] = 0; if (fopen_s(&fshudu, "myshudu.txt","r") != 0) { printf("打开数独文件报错！请检查myshudu.txt！\n"); fprintf(flog, "打开数独文件报错！请检查myshudu.txt！\n"); return -1; } for (i=1; i<=9; i++) { for (j=1; j<=9; j++) { cnt += fscanf_s(fshudu, "%d ", &num); if (num<0 || num>9) return -1; else shudu[i][j] = num; } } if (cnt != 81) return -1; fclose(fshudu); return 0; } /** @ 根据数独数组初始化对应的三维数组（除了传入参数点对应的数组） @ 参数：保留点的坐标，该点对应的数组不被初始化；若要全初始化，传入[0,0] */ int init_tt(int x, int y) { int i, j, k; for(i=1; i<=9; i++) for(j=1; j<=9; j++) { if (x==i && y==j) continue; if (shudu[i][j] != 0) for(k=1; k<=9; k++) tt[i][j][k] = -1; else for(k=1; k<=9; k++) tt[i][j][k] = 0; } return 0; } /**数独求解函数，采用递归方式从上到下从左到右求解 @ 参数：当前节点在数独的坐标位置； @ 返回值：0 成功 -1 无解 -2 位置错误 */ int looper(int x, int y) { int k, nexti, nextj; //参数检查 if (x<1 || x>9 || y<1 || y>9) return -2; //计算下一步的单元格的坐标 if (y==3 || y==6 || y==9) { if (x == 9) { nexti = 1; nextj = y+1; } else { nexti = x+1; nextj = y-2; } } else { nexti = x; nextj = y+1; } //单元格有初始值或已被赋值时 if (shudu[x][y] != 0) { if (x==9 && y==9) { printf("完成数独解算过程!\n"); return 0; } else { return looper(nexti, nextj); } } //单元格没有值时需要进行试值 for (k=1; k<=9; k++) { if (tt[x][y][k] == -1) continue; else { tt[x][y][k] = -1; if (no_repeat(x, y, k) == 0) { int tmpi; shudu[x][y] = k; fprintf(flog,"位置[%d,%d] := %d\n", x, y, k); if (x==9 && y==9) { printf("在对最后一格赋值后，完成数独解算过程!\n"); return 0; } //对所在的行、列筛除 for (tmpi=1; tmpi<=9; tmpi++) { tt[x][tmpi][k] = -1; tt[tmpi][y][k] = -1; } //对所在的3*3小方阵筛除 if (x<=3 && y<=3) { tt[1][1][k] = -1; tt[1][2][k] = -1; tt[1][3][k] = -1; tt[2][1][k] = -1; tt[2][2][k] = -1; tt[2][3][k] = -1; tt[3][1][k] = -1; tt[3][2][k] = -1; tt[3][3][k] = -1; } else if (x<=3 && y<=6) { tt[1][4][k] = -1; tt[1][5][k] = -1; tt[1][6][k] = -1; tt[2][4][k] = -1; tt[2][5][k] = -1; tt[2][6][k] = -1; tt[3][4][k] = -1; tt[3][5][k] = -1; tt[3][6][k] = -1; } else if (x<=3 && y<=9) { tt[1][7][k] = -1; tt[1][8][k] = -1; tt[1][9][k] = -1; tt[2][7][k] = -1; tt[2][8][k] = -1; tt[2][9][k] = -1; tt[3][7][k] = -1; tt[3][8][k] = -1; tt[3][9][k] = -1; } else if (x<=6 && y<=3) { tt[4][1][k] = -1; tt[4][2][k] = -1; tt[4][3][k] = -1; tt[5][1][k] = -1; tt[5][2][k] = -1; tt[5][3][k] = -1; tt[6][1][k] = -1; tt[6][2][k] = -1; tt[6][3][k] = -1; } else if (x<=6 && y<=6) { tt[4][4][k] = -1; tt[4][5][k] = -1; tt[4][6][k] = -1; tt[5][4][k] = -1; tt[5][5][k] = -1; tt[5][6][k] = -1; tt[6][4][k] = -1; tt[6][5][k] = -1; tt[6][6][k] = -1; } else if (x<=6 && y<=9) { tt[4][7][k] = -1; tt[4][8][k] = -1; tt[4][9][k] = -1; tt[5][7][k] = -1; tt[5][8][k] = -1; tt[5][9][k] = -1; tt[6][7][k] = -1; tt[6][8][k] = -1; tt[6][9][k] = -1; } else if (x<=9 && y<=3) { tt[7][1][k] = -1; tt[7][2][k] = -1; tt[7][3][k] = -1; tt[8][1][k] = -1; tt[8][2][k] = -1; tt[8][3][k] = -1; tt[9][1][k] = -1; tt[9][2][k] = -1; tt[9][3][k] = -1; } else if (x<=9 && y<=6) { tt[7][4][k] = -1; tt[7][5][k] = -1; tt[7][6][k] = -1; tt[8][4][k] = -1; tt[8][5][k] = -1; tt[8][6][k] = -1; tt[9][4][k] = -1; tt[9][5][k] = -1; tt[9][6][k] = -1; } else if (x<=9 && y<=9) { tt[7][7][k] = -1; tt[7][8][k] = -1; tt[7][9][k] = -1; tt[8][7][k] = -1; tt[8][8][k] = -1; tt[8][9][k] = -1; tt[9][7][k] = -1; tt[9][8][k] = -1; tt[9][9][k] = -1; } if (looper(nexti, nextj) != 0) { //递归，如果下一步不成功则前功尽弃，需要回退 int tmpk; shudu[x][y] = 0; init_tt(x, y); for (tmpk=k+1; tmpk<=9; tmpk++) tt[x][y][tmpk] = 0; //调试，回退本列上未尝试部分 } else return 0; //如果下一步成功，就跳出对k的遍历 } //对应 if (no_repeat(x, y, k) 的判断，如果这个试值不行，就去试下个值 } // if (tt[x][y][k] } //for return -1; } /**传入参数是当前节点在数独的位置，和试图的取值； @ 注意：根据数独的规则，合法的取值应该满足行、列、小方阵都没有重复 @ 返回值：0 可以取该值 -1 不可取该值 -2 位置错误 -3 试图赋的值错误 */ int no_repeat(int x, int y, int value) { int tmp; int ipos, jpos, m, n; if (x<1 || x>9 || y<1 || y>9) return -2; if (value<1 || value>9) return -3; for (tmp=1; tmp<=9; tmp++) if (y!=tmp && (shudu[x][tmp]==value)) return -1; for (tmp=1; tmp<=9; tmp++) if (x!=tmp && (shudu[tmp][y]==value)) return -1; if (x==1 || x==4 || x==7) ipos = 0; if (x==2 || x==5 || x==8) ipos = 1; if (x==3 || x==6 || x==9) ipos = 2; if (y==1 || y==4 || y==7) jpos = 0; if (y==2 || y==5 || y==8) jpos = 1; if (y==3 || y==6 || y==9) jpos = 2; for (m=0; m<3; m++) for (n=0; n<3; n++) if ((m!=ipos) && (n!=jpos) && (shudu[x-ipos+m][y-jpos+n]==value)) return -1; return 0; } void print_shudu(void) { int i, j; struct timeb tp1; struct tm *s_tm1; //打印这个数独题目 for(i=1; i<=9; i++) { for(j=1; j<=9; j++) printf("%d ", shudu[i][j]); printf("\n"); } printf("---------------------\n"); //记录交易时间 ftime(&tp1); s_tm1 = localtime(&(tp1.time)); printf("Start : d:d:d\n\n", s_tm1->tm_hour, s_tm1->tm_min, s_tm1->tm_sec); }

最新回复(0)