snr さんが書きました: ↑6年前
コード:
row = p / SIZE;
col = p % SIZE;
n が p になっています。
コード:
row = n / SIZE;
col = n % SIZE;
未定義関数を適当に定義してみました。
コード:
#include <stdio.h> // scanf, printf, putchar
#include <stdlib.h> // exit
#include <string.h> // memset
#define SIZE 9
void printBoard(int board[SIZE][SIZE], int *board_is) {
for (int i = 0; i < SIZE; i++, putchar('\n'))
for (int j = 0; j < SIZE; j++)
printf(" %d", board[i][j]);
}
int check_row(int board[SIZE][SIZE], int row, int n) {
for (int i = 0; i < SIZE; i++)
if (board[row][i] == n) return 0;
return 1;
}
int check_col(int board[SIZE][SIZE], int col, int n) {
for (int i = 0; i < SIZE; i++)
if (board[i][col] == n) return 0;
return 1;
}
int check_3x3(int board[SIZE][SIZE], int row, int col, int n) {
int r = row - row % 3;
int c = col - col % 3;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (board[r+i][c+j] == n) return 0;
return 1;
}
void initBoardZero(int board[SIZE][SIZE])
{
memset(board, 0, sizeof(int) * SIZE * SIZE);
}
void initInputBoard(int board[SIZE][SIZE], int *board_is)
{
char c;
for (int i = 0; i < SIZE; i++)
for (int j = 0; j < SIZE; j++) {
if (scanf(" %c", &c) != 1) exit(1);
if (c >= '0' && c <= '9') board[i][j] = c - '0';
else board[i][j] = 0;
}
}
void backtrack(int board[SIZE][SIZE] , int *board_is , int n){
if( (*board_is) == 0){
printf("no Solve\n");
return ;
}
int row , col;
int p;
if(n == SIZE*SIZE){
//solve Found
printf("solved\n");
printBoard(board , board_is);
return ;
}else{
/*
printf("********* n = %2d\t*********\n" , n);
printBoard(board , board_is);
printf("<");
*/
}
//printf(">");
row = n / SIZE;
col = n % SIZE;
//printf("+");
//printf("board[%d][%d] = %d\n" , row , col , board[row][col]);
if(board[row][col] != 0){
// printf("&");
backtrack(board , board_is , n+1);
}else{
//zen tan saku
//printf("@");
for(p = 0; p < SIZE; p++){
//printf("#");
if( check_row(board,row,(p+1))==1 &&
check_col(board,col,(p+1))==1 &&
check_3x3(board,row,col,(p+1))==1){
//printf("_");
board[row][col] = (p+1);
backtrack(board , board_is , n+1);
board[row][col] = 0;
}
}
}
}
void solve(int board[SIZE][SIZE] , int *board_is){
backtrack(board , board_is , 0);
}
int main(){
int board[SIZE][SIZE];
int board_is = 1;
//board_is 0:no solve
// 1:
initBoardZero(board);
initInputBoard(board , &board_is);
printBoard(board , &board_is);
solve( board , &board_is );
return 0;
}
入力
コード:
..36....7
.7..4..2.
.8....9..
..6..9...
89..1..63
...2..8..
..9....5.
.2..9..4.
7....56..
実行結果
コード:
0 0 3 6 0 0 0 0 7
0 7 0 0 4 0 0 2 0
0 8 0 0 0 0 9 0 0
0 0 6 0 0 9 0 0 0
8 9 0 0 1 0 0 6 3
0 0 0 2 0 0 8 0 0
0 0 9 0 0 0 0 5 0
0 2 0 0 9 0 0 4 0
7 0 0 0 0 5 6 0 0
solved
9 5 3 6 8 2 4 1 7
6 7 1 9 4 3 5 2 8
4 8 2 7 5 1 9 3 6
2 4 6 8 3 9 1 7 5
8 9 7 5 1 4 2 6 3
3 1 5 2 6 7 8 9 4
1 6 9 4 7 8 3 5 2
5 2 8 3 9 6 7 4 1
7 3 4 1 2 5 6 8 9
もっと簡潔にすると
コード:
#include <stdio.h> // scanf, printf, putchar
#include <stdlib.h> // exit
#define N 2 // 解の最大表示個数
int b[9][9], k;
int ok(int r, int c, int n)
{
for (int i = 0; i < 9; i++)
if (b[r][i] == n || b[i][c] == n) return 0;
r -= r % 3, c -= c % 3;
for (int p = r + 3; r < p; r++)
if (b[r][c] == n || b[r][c+1] == n || b[r][c+2] == n) return 0;
return 1;
}
void step(int r, int c)
{
if (c == 9) {
c = 0;
if (++r == 9) {
for (r = 0; r < 9; r++, putchar('\n'))
for (c = 0; c < 9; c++) printf(" %d", b[r][c]);
putchar('\n');
if (++k < N) return;
exit(0);
}
}
if (b[r][c]) step(r, c+1);
else
for (int n = 1; n <= 9; n++)
if (ok(r, c, n)) b[r][c] = n, step(r, c+1), b[r][c] = 0;
}
int main(void)
{
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++) {
char n;
if (scanf(" %c", &n) != 1) return 1;
b[r][c] = (n>='0' && n<='9') ? n - '0' : 0;
}
step(0, 0);
}