独数

给定一个部分填充的9×9二维数组，目标是将数字（从1到9）分配给空单元格，以便每个行、列包含恰好是从1到9的数字。如下图：

像所有其他回溯问题一样（N皇后问题），数独可以通过为空单元格一一分配数字来解决。在分配号码之前，检查当前行、当前列是否不存在相同的数字。并递归检查此分配是否可行。如果分配有冲突，尝试当前空单元格的下一个数字。如果当前单元格没有一个数字（1到9）可安置，则返回false，回溯重试上一个单元个下一个数字。

#python\n\ndefshow(grid):\nforiinrange(9):\nforjinrange(9):\nprint(f'{grid[i][j]}',end='')\nprint()\n\ndefget_empty_location(grid):\nforrowinrange(9):\nforcolinrange(9):\nif(grid[row][col]==0):\nreturnTrue,row,col\nreturnFalse,None,None\n\ndefnum_in_row(grid,row,num):\nforiinrange(9):\nif(grid[row][i]==num):\nreturnTrue\nreturnFalse\n\ndefnum_in_col(grid,col,num):\nforiinrange(9):\nif(grid[i][col]==num):\nreturnTrue\nreturnFalse\n\ndefis_safe(grid,row,col,num):\nreturnnotnum_in_row(grid,row,num)and\\\nnotnum_in_col(grid,col,num)\n\ndefsolve_sudoku(grid):\nret,row,col=get_empty_location(grid)\nifnotret:\nreturnTrue\n\nfornuminrange(1,10):\nif(is_safe(grid,row,col,num)):\ngrid[row][col]=num\n\nif(solve_sudoku(grid)):\nreturnTrue\n\ngrid[row][col]=0\n#回溯上个空格的下一个数字\nreturnFalse\n\nif__name__=="__main__":\ngrid=[[0forxinrange(9)]foryinrange(9)]\n\ngrid=[[2,0,6,5,0,0,4,0,0],\n[0,4,0,0,0,6,0,0,0],\n[0,8,7,0,0,0,0,3,1],\n[0,0,3,0,2,0,0,9,0],\n[0,0,0,8,0,3,0,0,6],\n[0,5,0,0,9,0,6,0,0],\n[1,0,0,3,0,0,2,5,0],\n[0,0,0,0,0,0,0,0,4],\n[0,0,0,2,0,5,3,0,0]]\nif(solve_sudoku(grid)):\nshow(grid)\nelse:\nprint("solutionnotexists")

//C\n\n#include\n\n#definetrue1\n#definefalse0\n\nvoidshow(chargrid[][9])\n{\n\tintrow,col;\n\nfor(row=0;row<9;row++){\nfor(col=0;col<9;col++)\nprintf("%d",grid[row][col]);\nprintf("\\n");\n\t}\n}\n\nstructpoint\n{\n\tintrow;\n\tintcol;\n};\n\nintget_empty_location(chargrid[][9],structpoint*p)\n{\n\tintrow,col;\n\n\tp->row=p->col=-1;\n\nfor(row=0;row<9;row++)\nfor(col=0;col<9;col++)\nif(grid[row][col]==0){\n\t\t\t\tp->row=row;\n\t\t\t\tp->col=col;\nreturntrue;\n\t\t\t}\nreturnfalse;\n}\n\nintnum_in_row(chargrid[][9],introw,intnum)\n{\n\tintcol;\n\nfor(col=0;col<9;col++)\nif(grid[row][col]==num)\nreturntrue;\nreturnfalse;\n}\n\nintnum_in_col(chargrid[][9],intcol,intnum)\n{\n\tintrow;\n\nfor(row=0;row<9;row++)\nif(grid[row][col]==num)\nreturntrue;\nreturnfalse;\n}\n\nintis_safe(chargrid[][9],introw,intcol,intnum)\n{\nreturn!num_in_row(grid,row,num)&&\n!num_in_col(grid,col,num);\n}\n\nintsolve_sudoku(chargrid[][9])\n{\n\tintnum;\n\tstructpointp;\n\nintret=get_empty_location(grid,&p);\nif(!ret)\nreturntrue;\n\nfor(num=1;num<=9;num++)\nif(is_safe(grid,p.row,p.col,num)){\ngrid[p.row][p.col]=num;\n\nif(solve_sudoku(grid))\nreturntrue;\n\ngrid[p.row][p.col]=0;\n\t\t}\n//回溯上个空格的下一个数字\nreturnfalse;\n}\n\nvoidmain(void)\n{\nchargrid[][9]=\n\t\t{{2,0,6,5,0,0,4,0,0},\n{0,4,0,0,0,6,0,0,0},\n{0,8,7,0,0,0,0,3,1},\n{0,0,3,0,2,0,0,9,0},\n{0,0,0,8,0,3,0,0,6},\n{0,5,0,0,9,0,6,0,0},\n{1,0,0,3,0,0,2,5,0},\n{0,0,0,0,0,0,0,0,4},\n\t\t\t{0,0,0,2,0,5,3,0,0}};\nif(solve_sudoku(grid))\nshow(grid);\nelse\nprintf("solutionnotexists");\n}