检查数独板是否正确填写

#1 楼

array = numpy.array([
       [9, 1, 4, 5, 7, 3, 8, 2, 6],
       [5, 3, 2, 4, 8, 6, 1, 7, 9],
       [9, 1, 3, 4, 2, 5, 8, 6, 7],
       [7, 1, 8, 2, 9, 3, 4, 5, 6],
       [9, 7, 1, 3, 2, 6, 5, 8, 4],
       [5, 3, 1, 7, 4, 2, 9, 8, 6],
       [1, 8, 6, 5, 3, 9, 2, 4, 7],
       [7, 1, 5, 9, 2, 4, 6, 8, 3],
       [1, 3, 7, 5, 8, 4, 2, 9, 6]])

>>> array[3, :]
array([7, 1, 8, 2, 9, 3, 4, 5, 6])
>>> array[:, 1]
array([1, 3, 1, 1, 7, 3, 8, 1, 3])
>>> array[:3, :3]
array([[9, 1, 4],
       [5, 3, 2],
       [9, 1, 3]])

>>> array[:3, :3].reshape(-1)
array([9, 1, 4, 5, 3, 2, 9, 1, 3])
>>> array[:3, :3].reshape(9)
array([9, 1, 4, 5, 3, 2, 9, 1, 3])

>>> numpy.unique(array[2, :])
array([1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> numpy.unique(array[:, 2])
array([1, 2, 3, 4, 5, 6, 7, 8])

def is_valid(line):
    return numpy.unique(line).shape == line.shape

def validate_sudoku(grid):
    board = numpy.asarray(grid)
    size, check_size = board.shape
    assert(size == check_size)

    for i in range(size):
        if not is_valid(board[i, :]):
            print 'Row', i+1, 'is invalid'
            return
        if not is_valid(board[:, i]):
            print 'Column', i+1, 'is invalid'
            return

    block_size = int(size**.5)
    for i in range(size):
        block_row, block_column = divmod(i, block_size)
        block = board[block_row*block_size:(block_row+1)*block_size, block_column*block_size:(block_column+1)*block_size]
        if not is_valid(block.reshape(size)):
            print 'Block', i+1, 'is invalid'
            return

     print 'Board is valid'

#2 楼

# All the logic pulled out of main and put into the checker functions
def main_function(board):
    print('Checking rows:')
    # Remove the boolean variable and just check the function's return
    # Also check the positive condition first to eliminate "not"
    if check_rows(board):
        print('All rows are correct')
    else:
        print('There are incorrect rows on the board')
        return

    print('Checking columns:')
    # Put the transpose operation inside a function called "check_colunms"
    if check_columns(board):
        print('All columns are correct')  
    else:
        print('There are incorrect columns on the board')
        return

    # Check if all nxn blocks are correct
    print('Checking blocks:')
    if check_blocks(board):
        print('All blocks are correct')
    else:
        print('There are incorrect blocks on the board')
        return

# Just a useful helper
def required_nums(board):
    return range(1, len(board[0]) + 1)

def check_rows(board):
    # Check that for all rows on board, all required numbers are present
    return all(all(n in row for n in required_nums(board)) for row in board)

def check_columns(board):
    return check_rows(transpose(board))

# Plagiarized this one right from stackoverflow from a google search for
#   "transpose python 2d list"
def transpose(board):
    return zip(*board)

# Now we want to do the block check logic simply just like the column case
def check_blocks(board):
    return check_rows(view_nsquares_as_rows(board))

# A helper just to retrieve a subsquare from our perfect-square sudoku board.
# In an NxN board we have N subsquare-blocks.
def get_nsquare(board, index):
    size = len(board[0])
    # No need to use a library to take square root
    subsize = int(size**(0.5))
    # Get block coordinates using standard array coordinate deflattening trick
    x, y = index % subsize, index / subsize # Note this is integer division
    # Multiply-out to get the subsquare bounds
    x1, x2 = subsize * x, subsize * (x+1)
    y1, y2 = subsize * y, subsize * (y+1)
    return [row[x1:x2] for row in board[y1:y2]]

# This is like a transpose, but putting each block into a row instead
#   of putting each column into a row.
def view_nsquares_as_rows(board):
    return [flatten_2d(get_nsquare(board, i)) for i in range(len(board[0]))]

# One more helper to flatten a 2d list into a single row, also
#  plagiarized from the first google result.
def flatten_2d(list2d):
    return [item for sublist in list2d for item in sublist]

#3 楼

def check_if_all_numbers(numbers):

    bincheck = 0
    goal = 0

    for n in numbers
        bincheck = bincheck | (1 << (n-1)) # set the n'th bit of binCheck to 1
        goal = goal << 1 | 1 # set one more bit to 1 in goal

    return (bincheck == goal) # check all numbers

With Numbers = 982 134 675 (correct)
Bincheck = 0b 0000 0000 0000, Goal = 0b 0000 0000 0000 #Init
Bincheck = 0b 0001 0000 0000, Goal = 0b 0000 0000 0001 #Add 9
Bincheck = 0b 0001 1000 0000, Goal = 0b 0000 0000 0011 #Add 8
Bincheck = 0b 0001 1000 0010, Goal = 0b 0000 0000 0111 #Add 2
Bincheck = 0b 0001 1000 0011, Goal = 0b 0000 0000 1111 #Add 1
Bincheck = 0b 0001 1000 0111, Goal = 0b 0000 0001 1111 #Add 3
Bincheck = 0b 0001 1000 1111, Goal = 0b 0000 0011 1111 #Add 4
Bincheck = 0b 0001 1010 1111, Goal = 0b 0000 0111 1111 #Add 6
Bincheck = 0b 0001 1110 1111, Goal = 0b 0000 1111 1111 #Add 7
Bincheck = 0b 0001 1111 1111, Goal = 0b 0001 1111 1111 #Add 5
Bincheck == Goal > it's ok

#4 楼

#5 楼

import numpy as np

def is_good_sudoku(board):
    board = np.asarray(board)
    assert board.ndim == 2  # Input must be a two-dimensional table.
    N = board.shape[0]
    assert board.shape[1] == N  # Input must be square.
    n = int(np.sqrt(N))
    assert n * n == N  # Input size must be a perfect square.

    numbers_1_N = np.arange(1, N + 1)

    # Check rows and columns
    if (not np.all(np.sort(board, axis=1) == numbers_1_N) or
            not np.all(np.sort(board.T, axis=1) == numbers_1_N)):
        return False

    # Check blocks
    blocks = board.reshape(n, n, n, n).transpose(0, 2, 1, 3).reshape(N, N)
    return np.all(np.sort(board.T, axis=1) == numbers_1_N)

#6 楼

import numpy

def check_array(structure, valid = 45):
    """
    Verifies that a sudoku column, row, or square is valid (assumes a 9x9 grid that requires the unique values 1 - 9 in each array).
    @param
        structure  – numpy.array – required  – a col, row, or square representation to validate
        valid      – integer     – optional  – valid sum value
    @return
        result     – boolean                 – is the array valid?
    """
    result = numpy.sum(array) == valid
    return result

def check_set(structure, valid = {1, 2, 3, 4, 5, 6, 7, 8, 9}):
    """
    Verifies that a sudoku column, row, or square is valid (assumes a 9x9 grid that requires the unique values 1 - 9 in each array).
    @param
        structure  – set         – required  – a col, row, or square representation to validate
        valid      – set         – optional  – set representation of valid row, col, or square
    @return
        result     – boolean     – is the array valid?
    """
    result = len(array & valid) == len(valid)
    return result

def check_set(structure, valid = {1, 2, 3, 4, 5, 6, 7, 8, 9}):
    """
    Verifies that a sudoku column, row, or square is valid (assumes a 9x9 grid that requires the unique values 1 - 9 in each array).
    @param
        structure  – set         – required  – a col, row, or square representation to validate
        valid      – set         – optional  – set representation of valid row, col, or square
    @return
        result     – boolean     – is the array valid?
    """
    if (len(array & valid) == len(valid)) and (sum(array) == sum(valid)):
        return true
    else:
        return false