首页 > 试题广场 >

合法数独

[编程题]合法数独
  • 热度指数：815 时间限制：C/C++ 5秒，其他语言10秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给定一个数独板的输入，确认当前的填法是否合法。
合法的输入需要满足以下三个条件：
1. 每一行的9个格子中是1-9的9个数字，且没有重复
2. 每一列的9个格子中是1-9的9个数字，且没有重复
3. 9个3*3的小格子中是1-9的9个格子，且没有重复

输入描述:
输入9行字符串，每行9个字符（不包含\r\n)，总共81个字符，空着的格子用字符‘X’表示

53XX7XXXX
6XX195XXX
X98XXXX6X
8XXX6XXX3
4XX8X3XX1
7XXX2XXX6
X6XXXX28X
XXX419XX5
XXXX8XX79


输出描述:
合法在输出字符串，“true”
非法则输出字符串，“false”
示例1

输入

53XX7XXXX
6XX195XXX
X98XXXX6X
8XXX6XXX3
4XX8X3XX1
7XXX2XXX6
X6XXXX28X
XXX419XX5
XXXX8XX79

输出

true
算法知识视频讲解
添加回答
xiaoehaier头像 xiaoehaier 
vector<int> row(9, 0);
vector<int> col(9, 0);
vector<int> block(9, 0);

int main()
{
    string r;
    for(int i=0; i<9; ++i){
        cin >> r;
        for(int j=0; j<9; ++j){
            if(r[j] == 'X') continue;
            int tmp = 1 << (r[j] - '0');
            if(row[i] & tmp || col[j] & tmp
              || block[i/3*3+j/3] & tmp){
                cout << "false";
                return 0;
            }
            
            row[i] |= tmp;
            col[j] |= tmp;
            block[i/3*3+j/3] |= tmp;
        }
    }
    cout << "true";
    return 0;
}

发表于 2020-04-30 10:46:03 回复(0)
pein531头像 pein531 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[][] board = new char[9][9];
        char[] rowArr;
        String row;
        while((row = br.readLine()) != null){
            rowArr = row.trim().toCharArray();
            for(int j = 0; j < 9; j++) board[0][j] = rowArr[j];
            for(int i = 1; i < 9; i++){
                rowArr = br.readLine().trim().toCharArray();
                for(int j = 0; j < 9; j++) board[i][j] = rowArr[j];
            }
            System.out.println(solve(board));
        }
    }
    
    private static boolean solve(char[][] board) {
        // 记录某行，某位数字是否已经被摆放
        boolean[][] row = new boolean[9][9];
        // 记录某列，某位数字是否已经被摆放
        boolean[][] col = new boolean[9][9];
        // 记录某 3x3 宫格内，某位数字是否已经被摆放
        boolean[][] block = new boolean[9][9];

        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] != 'X'){
                    int idx = board[i][j] - '1';           // 数字board[i][j]的行列索引
                    int blockIdx = i / 3 * 3 + j / 3;      // 九宫格块的索引
                    if (row[i][idx] || col[j][idx] || block[blockIdx][idx]) {
                        // 如果这个数字在限定范围内已经被使用过了，则返回false
                        return false;
                    } else {
                        // 否则更新状态
                        row[i][idx] = true;
                        col[j][idx] = true;
                        block[blockIdx][idx] = true;
                    }
                }
            }
        }
        // 通过所有检查，返回true
        return true;
    }
}

发表于 2020-10-19 22:09:06 回复(0)
爱笑的漠头像 爱笑的漠
这是leetcode第36题 原题 
res = []
for i in range(9):
    res.append(input())
from collections import defaultdict
row, col, grid = defaultdict(list), defaultdict(list), defaultdict(list)
flag = True
for i in range(9):
    for j in range(9):
        k = i//3*3 + j//3
        if res[i][j] != 'X':
            if res[i][j] in row[i]&nbs***bsp;res[i][j] in col[j]&nbs***bsp;res[i][j] in grid[k]:
                flag = False
                break
            else:
                row[i].append(res[i][j])
                col[j].append(res[i][j])
                grid[k].append(res[i][j])
    if not flag:
        break
if flag:
    print('true')
else:
    print('false')
        
          


发表于 2020-08-19 19:02:13 回复(0)
C/C++
BlackCarDriver头像 BlackCarDriver
填一下楼吧 
int data[10][10];

//检查一个数组是否全部数字不重复（除0外）
bool check(ARRAY ary){
	bool tmp[10];
	memset(tmp, false, sizeof(tmp));
	for (int &i : ary){
		if (i!=0 && tmp[i]) {
			return false;
		}
		tmp[i] = true;
	}
	return true;
}

int main(){
	//数据输入
	for (int i = 0; i < 9; i++){
		string row;
		cin >> row;
		for (int j = 0; j < 9; j++){
			data[i][j] = (isdigit(row[j]) ? row[j] - '0' : 0);	//初始值为0，且0不计重复
		}
	}
	bool stop = false;
	//检查10行
	for (int i = 0; i < 9 && !stop; i++){
		ARRAY rows(data[i], data[i] + 9);
		if (check(rows) == false){
			stop = true;
		}
	}
	//检查10列
	for (int i = 0; i < 9&& !stop; i++){
		ARRAY col(0);
		for (int j = 0; j <9; j++){
			col.push_back(data[j][i]);
		}
		if (check(col) == false){
			stop = true;
		}
	}
	//检查9个方格
	for (int i : {0, 3, 6}){	//九个九宫格的第左上角位置
		for (int j : {0, 3, 6 }){
			ARRAY tmp(0);
			for (int k = i; k < i + 3; k++){	//九宫格的9个数字
				for (int l = j; l < j + 3; l++){
					tmp.push_back(data[k][l]);
				}
			}
			if (check(tmp) == false){
				stop = true;
			}
		}
	}
	cout << (stop ? "false" : "true") << endl;
	return 0;
}


发表于 2020-04-12 21:28:46 回复(0)
人迹板桥霜头像 人迹板桥霜

Brute Force

mat = []
for _ in range(9):
    mat.append(input())

flag = 'true'
setl = [set() for _ in range(9)]
sets = [[set() for _ in range(3)] for _ in range(3)]
for i in range(9):
    tmp = set()
    for j in range(9):
        if mat[i][j] != 'X':
            if mat[i][j] in tmp:
                flag = 'false'
            elif mat[i][j] in setl[j]:
                flag = 'false'
            elif mat[i][j] in sets[i//3][j//3]:
                flag = 'false'
            else:
                tmp.add(mat[i][j])
                setl[j].add(mat[i][j])
                sets[i//3][j//3].add(mat[i][j])

print(flag)
发表于 2020-10-18 17:17:53 回复(0)
C/C++
牛客212899789号头像 牛客212899789号 
#include<iostream>
(720)#include<string>
using namespace std;

class Solution
{
public:
    string m_array[9];
    Solution()
    {
        for (int i = 0; i < 9; i++)
            cin >> m_array[i];
    }
    void m_chack()
        
    {
            for (int i = 0; i < 9 ; i++)
            {
                for (int j = 0; j<9; j++)
                {
                    char temp = m_array[i][j];
                    if (temp == 'X')
                        continue;
                    //列
                    for (int row = i; row < 9; row++)
                    {
                        if ( row == i)
                            continue;
                        if (temp == m_array[row][j])
                        {
                            cout << "false" << endl;
                            return;
                        }
                    
                    }
                    //行检查
                    for (int lin = j; lin < 9; lin++)
                    {
                        if (lin == j )
                            continue;
                        if (temp == m_array[i][lin])
                        {
                            cout << "false" << endl;
                            return;
                        }
                        
                    }
                    //小矩阵检查
                    for (int row = i; row < i / 3 * 3 + 3; row++)
                    {
                        for (int lin = j / 3 * 3; lin < j / 3 * 3 + 3; lin++)
                        {
                            if (lin == j && row == i)
                                continue;
                            if (temp == m_array[row][lin])
                            {
                                cout << "false" << endl;
                                return;
                            }
                        
                        }
                    }
                
                }
            }
        cout << "true" << endl;
        return;    
}
};
int main()
{
    Solution s;
    s.m_chack();
    return 0;
}

C++版

发表于 2020-04-20 23:22:20 回复(0)
牛客871108905号头像 牛客871108905号 
def check_row(nums):
    for i in range(9):
        temp = []
        for j in range(9):
            temp.append(nums[i][j])
        for t in range(9):
            if temp[t] != 'X' and temp.count(temp[t]) > 1 :
                return False
    return True

def check_col(nums):
    for i in range(9):
        temp = []
        for j in range(9):
            temp.append(nums[j][i])
        for t in range(9):
            if temp[t] != 'X' and temp.count(temp[t]) > 1 :
                return False
    return True

def check_square(nums):
    for out_i in [0,3,6]:
        for out_j  in [0,3,6]:
            temp = []
            for i in range(3):
                for j in range(3):
                    temp.append(nums[out_i+i][out_j+j])
            for t in range(9):
                if temp[t] != 'X' and temp.count(temp[t]) > 1:
                    return False
    return True




if __name__ == "__main__":
    nums = [[0 for col in range(9)] for row in range(9)]
    for i in range(9):
        nums[i] = list(map(str, input()))
    if check_row(nums) == True and check_col(nums) == True and check_square(nums) == True:
        print("true")
    else:
        print("false")

发表于 2020-04-16 21:24:03 回复(0)
gggone头像 gggone
牛客网上题解太少了
发表于 2020-04-14 00:38:05 回复(0)
offer尽管砸向我头像 offer尽管砸向我
我吐了，没认真审题，一直以为要判断在给定的条件下是否能够填写出来真个表，结果看答案的时候也没搞懂通过的逻辑，回去读题才发现原来看错题了，而且判断条件就明摆着……
发表于 2020-04-12 14:02:02 回复(0)
牛客753087731号头像 牛客753087731号 
def checkRow(a):
    for i in range(9):
        if len(a[i]) != 9: return False
        count = [0] * 9
        for char in a[i]:
            if char=='X': continue
            count[int(char)-1] += 1
        if max(count) > 1: return False
    return True
def transpose(a):
    for i in range(9):
        for j in range(i,9):
            a[i][j], a[j][i]= a[j][i], a[i][j]
    return a
def getBoxArray(a):
    new =[[] for _ in range(9)]
    for k in range(3):
        for i in range(3):
            for j in range(3):
                new[i+3*k] += a[j+k*3][3*i:3*i+3]
    return new

if __name__ == '__main__':
    get=[[] for _ in range(9)]
    for i in range(9):
        get[i] = list(map(str, input()))
    if checkRow(get) and checkRow(transpose(get)) and checkRow(getBoxArray(get)):
        print('true')
    else:
        print('false')
编辑于 2020-04-11 14:28:46 回复(0)
是哥哥啊头像 是哥哥啊 
import sys
 
def isValid(string):
    if (len(string) < 9):
        return False
    count = [0 for _ in range(9)]
    for ch in string:
        if (ch == 'X'): continue
        count[int(ch) - 1] += 1
        if (count[int(ch) - 1] > 1):
            return False
    return True
     
if __name__ == '__main__':
     
    table = []
    for i in range(9):
        table += [sys.stdin.readline().strip()]
     
    for i in range(9):
        str1 = table[i]
        str2 = ''.join(map(lambda x: x[i], table))
        r, c = i // 3, i % 3
        str3 = ''.join(map(lambda x: x[3 * c: 3 * c + 3], table[3 * r: 3 * r + 3]))
        if sum(map(isValid, [str1, str2, str3])) < 3:
            print("false")
            sys.exit(0)
 
    print("true")

发表于 2020-04-10 15:44:22 回复(0)
Python
Spco头像 Spco 
tem1 = [None] * 9
#输入
for i in range(9):
    tem1[i] = list(input())

flag = 1
for i in range(9):
    for j in range(9):
        if tem1[i][j] != 'X' and tem1[i].count(j) > 1:
            flag = 0

if flag == 1:
    (3239)#做一个转置，然后利用上边的方法判断
    tem2 = [[None] * 9 for _ in range(9)]
    for i in range(9):
        for j in range(9):
            tem2[j][i] = tem1[i][j]
            
    for i in range(9):
        for j in range(9):
            if tem2[i][j] != 'X' and tem2[i].count(j) > 1:
                flag = 0

#判断3*3的小方块是否满足要求
(3240)#首先将小方块中展开为一列
if flag == 1:
    tem3 = []
    for ii in range(3):
        for jj in range(3):
            for iii in range(ii*3, (ii+1)*3):
                for jjj in range(jj*3, (jj+1)*3):
                    tem3.append(tem1[iii][jjj])
            for m in tem3:
                if m != 'X' and tem3.count(m) > 1:
                    flag = 0
                    break
            tem3 = []
                    
if flag == 1:
    print('true')
else:
    print('false')
参考的是已通过的那位大佬的答案，这里做个记录
思路就是分别判断每一行是否满足要求
判断列的时候做一个交换，判断3*3的时候重组为一行
发表于 2020-03-21 22:50:04 回复(0)
bettermin头像 bettermin 
为什么通过不了所以案例？？？
class Solution:
    def isValidSudoku(self,board):
        def isValid(listnums):
            # 去掉空格后是否存在重复数字，不存在则返回1
            nums = list(filter(lambda x:x!='X',listnums))
            return len(set(nums)) == len(nums)
        for row in board:
            if not isValid(row):
                return False
        for column in zip(*board):
            if not isValid(column):
                return False
        for row in range(3):
            for col in range(3):
                bolck = [board[i][i] for i in range(row*3,row*3+3) for j in range(col*3,col*3+3)]
                if not isValid(block):
                    return False
        return True
board= []
for i in range(9):
    row = list(input())
    board.append(row)
solution = Solution().isValidSudoku(board)
if solution == True:
    print('true')
else:
    print('false')

发表于 2020-03-21 17:09:42 回复(0)
QK康哥在此头像 QK康哥在此
一定要读对题，以为是解数独，在想为什么有些用例一直过不了，服了。
发表于 2020-03-13 23:52:12 回复(2)
提交观点

问题信息

快手 算法工程师 2020
上传者：小小
难度：
14条回答 2918浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号