Sudoku 程序的编写

Question

Problem Description
AmazingCaddy likes Sudoku very much. One day, he got some Sudoku problems and he wondered whether these problems are well designed. He needs your help now.

Sudoku is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9 × 9 grid with digits so that each column, each row, and each of the nine 3 × 3 regions contain all of the digits from 1 to 9.
-- Wikipedia

In this problem, the grid has three different sizes, with the formal (N^2) × (N^2), and N will be one in 2, 3 and 4. The rule is the same. The objective is to fill the (N^2) × (N^2) grid with characters so that each column, each row, and each of the N^2 regions (each size is N × N) contains all of the characters from 1 to 4(N = 2), 1 to 9(N = 3) or 1 to G (N = 4).

You task is that when you got a grid, you should tell the grid whether a puzzle or not. If it`s a puzzle, you should tell whether it is a minimal puzzle; else you should tell it has no solution or has multiple solutions.

A puzzle is a partially completed grid (the size is (N^2) × (N^2), N = 2, 3, 4), and has one and only one solution. If remove any character from a puzzle, it will lead to multiple solutions, then it is called a minimal puzzle.

Input
The input contains several cases. For each case, the first line of the input is the N (2<= N <=4). The next N^2 lines will contain the grid. Each line will have N^2 characters, represent the grid. The empty cell will be represented as ’.’. All input data is legal, and you can get more information from the sample input.

Output
For each case:
If the grid is not a puzzle, and has no solution, print “No Solution”, or has multiple solutions print “Multiple Solutions”.
If the grid is a puzzle, but not a minimal, print “Not Minimal”, or print N lines represent the answer in the same format in the input, and ‘.’ should be replaced with the right characters. You can get more information from the sample output.

Sample Input
2
4312
12.4
....
...1
3
5...9.31.
71.8...9.
32...6...
........3
.8.5.3...
4....1.5.
8..9...4.
...1..9..
.....7...
4
...86.....D.A...
.A.C.G.49....65E
.......3B61C..DG
3...89.D7....24.
....4..G.9F2BD..
49...C5.....7...
1.C..8.B6.......
.6A.2.D...4.89.5
8F3BG.E24.A...7.
...6.3.A.1......
D.........5.1E2.
.G...D.9........
......F6.7.....3
6D.9.7..EG...B..
51B.A..8........
........F.C..71.

Sample Output
Not Minimal
Multiple Solutions
9BG86F253ED4A1C7
7ADC1GB4928F365E
F245EA73B61C98DG
3E6189CD7AG5F24B
E873461G59F2BDAC
492D3C5FA8EB7G61
15CF98AB6D7G43E2
B6AG2ED7C34189F5
8F3BG1E24CAD6579
C756F38A219EG4BD
D49A7B6CGF531E28
2G1E5D498B67CF3A
GCE4D5F617B82A93
6DF9C731EG2A5B84
51B7A298D436ECGF
A382B4GEF5C9D716

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

# Import necessary packages
library(readline)

# Define function to check if the grid is a puzzle
is_puzzle <- function(grid, n) {
    # Check if grid is empty
    if (!grepl(".*", grid)) return("Empty")
    
    # Check for valid rows
    for (i in 1:nrow(grid)) {
        if (!all(grepl(1:4, gsub("[.]","", grid[i])))) return("Invalid Rows")
    }
    
    # Check for valid columns
    for (j in 1:ncol(grid)) {
        col_sum <- sum(sapply(grid, function(x) x[j]))
        if (col_sum != nrow(grid)*n || !grepl(1:4, sapply(grid, function(x) x[j]))) return("Invalid Columns")
    }
    
    # Check for valid regions
    for (k in 1:(n^2/n)) {
        region_sum <- sum(sapply(matrix(grid[k*n:(k+1)*n], nrow=n, ncol=n), function(x) x[k]))
        if (region_sum != nrow(grid)^2*(n-1)/n || !grepl(1:4, sapply(matrix(grid[k*n:(k+1)*n], nrow=n, ncol=n), function(x) x[k]))) return("Invalid Regions")
    }
    
    # Check for single solution
    if (length(unique(sapply(grid, function(x) x[!grepl(".", x)]))) > 1) return("Not Minimal")
    return("Puzzle")
}

# Function to solve the puzzle by backtracking
solve_puzzle <- function(grid, n) {
    if (n == 2) {
        # Solve for two-dimensional puzzles
        return(solve_2d_puzzle(grid))
    } else if (n == 3) {
        # Solve for three-dimensional puzzles
        return(solve_3d_puzzle(grid))
    } else if (n == 4) {
        # Solve for four-dimensional puzzles
        return(solve_4d_puzzle(grid))
    } else {
        return("Invalid Dimensions")
    }
}

# Function to solve the 2D puzzle
solve_2d_puzzle <- function(grid) {
    # Backtrack through grid
    for (i in 1:length(grid)) {
        for (j in 1:length(grid[i])) {
            if (grid[i][j] == ".") {
                # Try filling with possible values
                for (val in c(1:4)) {
                    if (is.na(val) || val == grid[i][j]) continue
                    grid[i][j] <- val
                    if (is_puzzle(grid, n)) return(grid)
                    grid[i][j] <- ""
                }
            }
        }
    }
    return("")
}

# Function to solve the 3D puzzle
solve_3d_puzzle <- function(grid) {
    # Backtrack through grid
    for (i in 1:length(grid)) {
        for (j in 1:length(grid[i])) {
            for (k in 1:length(grid[i,j])) {
                if (grid[i][j][k] == ".") {
                    # Try filling with possible values
                    for (val in c(1:4)) {
                        if (is.na(val) || val == grid[i][j][k]) continue
                        grid[i][j][k] <- val
                        if (is_puzzle(grid, n)) return(grid)
                        grid[i][j][k] <- ""
                    }
                }
            }
        }
    }
    return("")
}

# Function to solve the 4D puzzle
solve_4d_puzzle <- function(grid) {
    # Backtrack through grid
    for (i in 1:length(grid)) {
        for (j in 1:length(grid[i])) {
            for (k in 1:length(grid[i][j])) {
                for (l in 1:length(grid[i][j,k])) {
                    if (grid[i][j][k][l] == ".") {
                        # Try filling with possible values
                        for (val in c(1:4)) {
                            if (is.na(val) || val == grid[i][j][k][l]) continue
                            grid[i][j][k][l] <- val
                            if (is_puzzle(grid, n)) return(grid)
                            grid[i][j][k][l] <- ""
                        }
                    }
                }
            }
        }
    }
    return("")
}

# Read input grid from user
input_grid <- readline(prompt="Enter the grid:\n")

# Convert input grid to matrix
input_matrix <- as.matrix(input_grid)

# Check if grid is a puzzle
if (is_puzzle(input_matrix, n)) {
    print(paste("Puzzle:", is_puzzle(input_matrix, n)))
} else {
    # Print No Solution message
    print("No Solution")
}

This R code defines functions to check if a given grid is a puzzle and to solve the puzzle. It uses backtracking techniques to explore all possible combinations of values for the grid cells until a valid configuration is found.