Проверьте, действительно ли решение судоку [закрыто]

Вам дано решение головоломки судоку. Напишите код, чтобы проверить, является ли это допустимым решением.

Ваша сигнатура функции должна быть:
логический isValid(int starti, int startj, int endi, int endj)

Правила для тех, кто не знаком с судоку:

  • размер сетки 9x9, разделенной на 9 областей по 3x3
  • каждая строка должна содержать все цифры от 1-9
  • каждый столбец должен содержать все цифры от 1-9
  • каждый квадрат 3x3 должен содержать все цифры от 1-9

Мне не задавали этот вопрос, но я видел его на нескольких места . Проверка последнего правила может быть интересной частью

11 4
sudoku

11 ответов:

// rows
for (int i=0; i<9; i++) {
    std::bitset<9> filled;
    for (int j=0; j<9; j++)
        filled.set(grid[i][j] - 1);
    if (filled.count() != 9)
        return false;
}

// ... similar with the loops "swapped" to get the columns
// (or do both in one loop)

for (int i=0; i<9; i += 3)
    for (int j=0; j<9; j += 3) {
        std::bitset<9> filled;
        for (int k=0; k<3; k++)
            for (int l=0; l<3; l++)
                filled.set(grid[i+k][j+l] - 1);
        if (filled.count() != 9)
            return false;
    }

return true;
10

Извини, я знаю, что это должно быть домашнее задание, но ничего не могу с собой поделать. Это просто слишком весело, чтобы придумать что-то: -)

Ложка, полная LINQ, заставляет лекарство идти вниз: 
public class Sudoku
{
    private int[][] sudoku;

    public Sudoku(int[][] sudoku)
    { 
        // TODO: Validate bounds and values
        this.sudoku = sudoku;
    }

    public bool Validate() =>
        VerticalLines.All(IsValid)
        && HorizontalLines.All(IsValid)
        && Squares.All(IsValid);

    IEnumerable<IEnumerable<int>> VerticalLines =>
        from line in sudoku select line;

    IEnumerable<IEnumerable<int>> HorizontalLines =>
        from y in Enumerable.Range(0, 9)
        select (
            from x in Enumerable.Range(0, 9)
            select sudoku[x][y]);

    IEnumerable<IEnumerable<int>> Squares =>
        from x in Enumerable.Range(0, 3)
        from y in Enumerable.Range(0, 3)
        select GetSquare(x, y);

    IEnumerable<int> GetSquare(int x, int y) =>
        from squareX in Enumerable.Range(0, 3)
        from squareY in Enumerable.Range(0, 3)
        select sudoku[x * 3 + squareX][y * 3 + squareY];

    bool IsValid(IEnumerable<int> line) => !(
        from item in line
        group item by item into g
        where g.Count() > 1
        select g)
        .Any();
}

Самое приятное в этом решении то, что ни один учитель не поверит вам, если вы скажете, что придумали это ; -)

6

SQL позволяет определить правила как ограничения: недопустимые головоломки запрещены и не могут существовать.

        -- Domain with only values 1..9 allowed,
        -- used for both the {x,y,z} coordinates and the cell values.
CREATE DOMAIN one_nine
        AS INTEGER
        CHECK (value >= 1 AND value <= 9)
        ;

        -- Table containing exactly one sudoku puzzle.
        -- The zzz coordinate (the "box number") is formally redundant
        -- (since it is functionally dependant on {xxx,yyy})

DROP TABLE IF EXISTS sudoku3 CASCADE;
CREATE TABLE sudoku3
        ( yyy one_nine NOT NULL
        , xxx one_nine NOT NULL
        , zzz one_nine NOT NULL
        , val one_nine
        );

        -- First constraint: (x,y) is unique
ALTER TABLE sudoku3 ADD PRIMARY KEY (xxx,yyy);

        -- Three constraints for unique values for {rows,columns,boxes}
CREATE UNIQUE INDEX sudoku_xv ON sudoku3 (xxx,val);
CREATE UNIQUE INDEX sudoku_yv ON sudoku3 (yyy,val);
CREATE UNIQUE INDEX sudoku_zv ON sudoku3 (zzz,val);

        -- Create empty board.
INSERT INTO sudoku3 (yyy, xxx, zzz)
SELECT  1+(nn/9)
        , 1+(nn%9)
        , 1+3*((nn/3)%3)+1*(nn/27)
        -- generate_series() is postgres-specific
        FROM generate_series(0,80) AS nn;

Теперь элементы - >val можно обновить, но результирующая таблица никогда не может нарушить ни одно из четырех ограничений (три из них на самом деле являются индексами, но это не имеет значения здесь).

Проверка на наличие полностью корректной заполненной таблицы означает: проверка наличия 81 ненулевой записи: 

SELECT 1 AS result -- COUNT(*) 
    FROM sudoku3
    WHERE val IS NOT NULL
    HAVING COUNT(*) = 81
      ;
5

Реализация Java с использованием наборов битов: 

public static boolean isValid(int[][] board) {
  //Check rows and columns 
  for (int i = 0; i < board.length; i++) {
    BitSet bsRow = new BitSet(9);
    BitSet bsColumn = new BitSet(9);
    for (int j = 0; j < board[i].length; j++) {
      if (board[i][j] == 0 || board[j][i] == 0) continue;
      if (bsRow.get(board[i][j] - 1) || bsColumn.get(board[j][i] - 1))
        return false;
      else {
        bsRow.set(board[i][j] - 1);
        bsColumn.set(board[j][i] - 1);
      }
    }
  }
  //Check within 3 x 3 grid
  for (int rowOffset = 0; rowOffset < 9; rowOffset += 3) {
    for (int columnOffset = 0; columnOffset < 9; columnOffset += 3) {
      BitSet threeByThree = new BitSet(9);
      for (int i = rowOffset; i < rowOffset + 3; i++) {
        for (int j = columnOffset; j < columnOffset + 3; j++) {
          if (board[i][j] == 0) continue;
          if (threeByThree.get(board[i][j] - 1))
            return false;
          else
            threeByThree.set(board[i][j] - 1);
        }
      }  
    }
  }
  return true;
}
2

Это было бы мое решение в ruby 

#Sudoku grid 9x9 with numbers between 1 and 9
#three rules:
#1) in any row all numbers between 1 and 9 have to be present
#2) in any columns all numbers between 1 and 9 have to be present
#3) in any of the 9 3x3 boxes all numbers between 1 and 9 have to be present 


sudoku_correct =[[8,3,5,4,1,6,9,2,7],
               [2,9,6,8,5,7,4,3,1],
               [4,1,7,2,9,3,6,5,8],
               [5,6,9,1,3,4,7,8,2],
               [1,2,3,6,7,8,5,4,9],
               [7,4,8,5,2,9,1,6,3],
               [6,5,2,7,8,1,3,9,4],
               [9,8,1,3,4,5,2,7,6],
               [3,7,4,9,6,2,8,1,5]]

sudoku_incorrect =[[8,3,5,4,1,6,9,2,7],
                 [2,9,6,8,5,7,4,3,1],
                 [4,1,7,2,9,3,6,5,8],
                 [5,6,9,1,3,4,7,8,2],
                 [1,2,3,6,7,8,5,4,9],
                 [7,4,8,5,2,9,1,6,3],
                 [6,5,2,7,8,1,3,9,4],
                 [9,8,1,3,4,5,2,7,6],
                 [3,7,4,9,6,2,8,1,1]]

class Sudoku
def initialize(s_arr)
  @sudoku_arr = s_arr
end

# given 9 integers makesure that you have 1 to 9
def valid_contents?(set)
  set.each do |e|
    return false unless (1..9).include?(e)
  end
  return true
end

# check if set has no duplicates
def has_no_duplicates?(set)
  set.uniq.size < set.size ? false : true
end

def valid_set?(set)
  valid_contents?(set) &&  has_no_duplicates?(set)
end

# obtain blocks of sudoku, given a grid
def get_blocks(s_grid)
  blocks = []
  s_grid.each_slice(3) do |row_set|
    blocks_temp = [[],[],[]]
    row_set.each do |row|
      row.each_slice(3).with_index  do|s,i|
        blocks_temp[i] = blocks_temp[i] + s
      end
    end
    blocks +=  blocks_temp
  end
  blocks
end


def valid?(s_arr = @sudoku_arr)
  #check for row validity
  s_arr.each do |set|
    return false unless valid_set?(set)
  end

  #check for block validity
  get_blocks(s_arr).each do |set|
    return false unless valid_set?(set)
  end

  #check column validity
  s_arr.transpose.each do |set|
    return false unless valid_set?(set)
  end

  true
end

end


puts  Sudoku.new(sudoku_correct).valid?
puts  Sudoku.new(sudoku_incorrect).valid? 
# output: True & False
1
package Questions;

public class SudukoSonChek {

    public static void main(String args[]) {

        int a[][] = { { 2, 4, 8, 3, 9, 5, 7, 1, 6 },
                { 5, 7, 1, 6, 2, 8, 3, 4, 9 }, { 9, 3, 6, 7, 4, 1, 5, 8, 2 },
                { 6, 8, 2, 5, 3, 9, 1, 7, 4 }, { 3, 5, 9, 1, 7, 4, 6, 2, 8 },
                { 7, 1, 4, 8, 6, 2, 9, 5, 3 }, { 8, 6, 3, 4, 1, 7, 2, 9, 5 },
                { 1, 9, 5, 2, 8, 6, 4, 3, 7 }, { 4, 2, 7, 9, 5, 3, 8, 6, 1 } };

        System.out.println(check(a));
    }

    public static boolean check(int arr[][]) {
        int i, j;
        int count[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        int count1[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        boolean b = true;
        for (i = 0; i < 9; i++) {
            for (j = 0; j < 9; j++) {

                if (count[arr[j][i]] > i) {
                    b = false;
                    return b;
                }
                if (count1[arr[i][j]] > i) {
                    b = false;
                    return b;
                }
                count1[arr[i][j]]++;
                count[arr[j][i]]++;
            }

        }
        return b;
    }

}
0

В отношении превосходного ответа от @Stephen, вот решение в C#, не прибегая к LINQ, чтобы показать разницу между этими двумя подходами.

Это решение работает как с 4х4, так и с 9х9 досками Sodoku.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace Sodoku
{
    class Program
    {
        static void Main(string[] args)
        {
            List<string> lines = new List<string>();
            lines.Add("4;1,4,2,3,2,3,1,4,4,2,3,1,3,1,4,2");
            lines.Add("4;2,1,3,2,3,2,1,4,1,4,2,3,2,3,4,1");
            lines.Add("9;5,3,4,6,7,8,9,1,2,6,7,2,1,9,5,3,4,8,1,9,8,3,4,2,5,6,7,8,5,9,7,6,1,4,2,3,4,2,6,8,5,3,7,9,1,7,1,3,9,2,4,8,5,6,9,6,1,5,3,7,2,8,4,2,8,7,4,1,9,6,3,5,3,4,5,2,8,6,1,7,9");
            lines.Add("9;8,7,1,4,6,9,3,5,2,4,2,6,3,5,1,8,9,7,5,9,3,7,2,8,4,6,1,3,5,2,9,4,7,6,1,8,6,4,9,1,8,2,5,7,3,1,8,7,5,3,6,2,4,9,9,6,4,2,1,3,7,8,5,7,3,8,6,9,5,1,2,4,2,1,5,8,7,4,9,3,6");
            lines.Add("9;1,2,7,5,3,9,8,4,6,4,5,3,8,6,1,7,9,2,8,9,6,4,7,2,1,5,3,2,8,9,3,1,7,4,6,5,3,6,5,2,8,4,9,1,7,7,4,1,9,5,6,3,2,8,9,7,4,6,2,8,5,3,1,5,1,2,7,4,3,6,8,9,6,3,8,1,9,5,2,7,4");
            lines.Add("4;1,4,4,3,2,3,4,4,3,2,3,1,3,1,4,2");

            foreach (var line in lines)
            {
                var tokens = line.Split(';');

                var NxN = int.Parse(tokens[0]);
                var nums = tokens[1].Trim().Split(',').Select(int.Parse).ToArray();

                // Copy into Grid. Input is in row major form.
                var grid = new int[NxN, NxN];
                {
                    int i = 0;
                    for (int row = 0; row < NxN; row++)
                    {
                        for (int col = 0; col < NxN; col++)
                        {
                            grid[row, col] = nums[i];
                            i++;
                        }
                    }
                }

                int violations = 0;

                // Check if each column passes tests for Sodoku.
                {                   
                    for (int row = 0; row < NxN; row++)
                    {
                        var tempArray = new int[NxN];

                        for (int col = 0; col < NxN; col++)
                        {
                            tempArray[col] = grid[row, col];
                        }

                        if (IfArrayPassesSodoku(tempArray) == false)
                        {
                            violations++;
                        }
                    }
                }

                // Check if each row passes tests for Sodoku.
                {
                    for (int row = 0; row < NxN; row++)
                    {
                        var tempArray = new int[NxN];

                        for (int col = 0; col < NxN; col++)
                        {
                            tempArray[col] = grid[col, row];
                        }

                        if (IfArrayPassesSodoku(tempArray) == false)
                        {
                            violations++;
                        }
                    }
                }

                // Check if each sub-grid passes tests for Sodoku.
                // In 9x9 Sodoku, there are 9 subgrids of 3x3 each.
                {
                    int NxNsub = (int)Math.Sqrt(NxN); // Length of side of sub-grid, for a 9x9 board this will be 3.

                    for (int row = 0; row < NxN; row += NxNsub)
                    {
                        for (int col = 0; col < NxN; col += NxNsub)
                        {
                            var tempArray = new int[NxN];
                            int index = 0;
                            for (int i = 0; i < NxNsub; i++)
                            {
                                for (int j = 0; j < NxNsub; j++)
                                {
                                    tempArray[index] = grid[i + col, j + row];
                                    index++;
                                }    
                            }
                            if (IfArrayPassesSodoku(tempArray) == false)
                            {
                                violations++;
                            }
                        }
                    }

                }

                Console.WriteLine(violations == 0 ? "True" : "False");

                // Correct output is:
                // True
                // False
                // True
                // True
                // True
                // False
            }

            Console.ReadKey();
        }

        /// <summary>
        /// Checks to see if one-dimensional array passes Sodoku rules:
        /// 1. Digits range from 1 to N.
        /// 2. No repeating digits.        
        /// Could be way more efficient, but this solution is more readable compared to other concise forms.
        /// </summary>
        /// <param name="array">Array.</param>
        /// <returns>True if one-dimensional array passes Sodoku rules.</returns>
        static bool IfArrayPassesSodoku(int[] array)
        {
            int violations = 0;

            // Check for repeating digits.
            bool ifRepeatedDigits = (array.Distinct().ToArray().Length != array.Length);
            if (ifRepeatedDigits == true)
            {
                return false;
            }

            // Check to see that it contains the digits 1 to N.
            var sorted = array.OrderBy(o => o).ToArray();

            if (array.Length == 4)
            {
                if (sorted[0] != 1 || sorted[3] != 4)
                {
                    return false;
                }
            }
            else if (array.Length == 9)
            {
                if (sorted[0] != 1 || sorted[8] != 9)
                {
                    return false;
                }
            }
            else
            {
                Console.Write("Error E5234. Invalid grid size.\n");
                return false;
            }

            return true;
        }
    }
}
0

У меня была аналогичная задача, вход исходил из стандартного ввода.

Я использовал наборы. Поместите элемент в правую строку, столбец и квадрат (в моем коде это называется box). Если размер всех 3 наборов равен 9, это допустимо.

#include <iostream>
#include <set>

int main()
{

//decl
std::set<int> row[9];
std::set<int> column[9];
std::set<int> box[9];


//read & store
for (int i = 0; i < 9; ++i)
{
    for (int j = 0; j < 9; ++j)
    {
        int val;
        std::cin >> val;
        if ((val >= 1) && (val <= 9))
        {
            row[i].insert(val);
            column[j].insert(val);
            int k = j / 3 + i / 3 + i / 3 + i / 3;
            box[k].insert(val);
        }
    }
}

//check
bool l = true;
int i = 0;
while (l && i < 9)
{
    l = row[i].size() == 9;
    ++i;
}

if (!l) std::cout << "Invalid" << std::endl;
else
{
    bool l = true;
    int i = 0;
    while (l && i < 9)
    {
        l = column[i].size() == 9;
        ++i;
    }

    if (!l) std::cout << "Invalid" << std::endl;
    else
    {
        bool l = true;
        int i = 0;
        while (l && i < 9)
        {
            l = box[i].size() == 9;
            ++i;
        }

        if (!l) std::cout << "Invalid" << std::endl;
        else std::cout << "Valid" << std::endl;
    }
}

return 0;

}

0

Я думал, что мое решение было кратким, но, видимо, так же, как и у всех остальных. в любом случае, я думаю, что это очень ясный и легко читаемый ответ в ruby, который я сделал для вопроса интервью 7/11/2014: 

## Returns true iff the given string is a valid sudoku solution
def is_valid_solution(grid)
  return false unless grid.is_a? String and grid.size == 9 * 9
  validate_rows(grid) and validate_columns(grid) and validate_boxes(grid)
end

## Returns true iff the set is the chars "1", "2", ..., "9"
def is_valid_set(set)
  return false if set.size != 9
  (1..9).each do | x |
    return false unless set.include?(x.to_s)
  end
  true
end

def validate_rows(grid)
  (0...9).each do | row |
    index = row * 9
    return false unless is_valid_set(grid[index, 9])
  end
  true
end

def validate_columns(grid)
  (0...9).each do | index |
    column = (index...81).step(9).to_a.map { | i | grid[i] }.join
    return false unless is_valid_set(column)
  end
  true
end

## This is ugly, but I'm running out of time...
TOP_LEFT_INDICES =  [ 0,  1,  2,  9, 10, 11, 18, 19, 20]
TOP_MID_INDICES =   [ 3,  4,  5, 12, 13, 14, 21, 22, 23]
TOP_RIGHT_INDICES = [ 6,  7,  8, 15, 16, 17, 24, 25, 26]
MID_LEFT_INDICES =  [27, 28, 29, 36, 37, 38, 45, 46, 47]
MID_MID_INDICES =   [30, 31, 32, 39, 40, 41, 48, 49, 50]
MID_RIGHT_INDICES = [33, 34, 35, 42, 43, 44, 51, 52, 53]
BOT_LEFT_INDICES =  [54, 55, 56, 63, 64, 65, 72, 73, 74]
BOT_MID_INDICES =   [57, 58, 59, 66, 67, 68, 75, 76, 77]
BOT_RIGHT_INDICES = [60, 61, 62, 69, 70, 71, 78, 79, 80]
BOX_INDICES = [TOP_LEFT_INDICES, TOP_MID_INDICES, TOP_RIGHT_INDICES,
               MID_LEFT_INDICES, MID_MID_INDICES, MID_RIGHT_INDICES,
               BOT_LEFT_INDICES, BOT_MID_INDICES, BOT_RIGHT_INDICES]

def validate_boxes(grid)
  BOX_INDICES.each do | indices |
    box = indices.map { | i | grid[i] }.join
    return false unless is_valid_set(box)
  end
  true
end
0

Строки и столбцы могут быть проверены в одном цикле 

public class SudokuChecker {

static int[][] sMatrix = {

    {5,3,4,6,7,8,9,1,2},
    {6,7,2,1,9,5,3,4,8},
    {1,9,8,3,4,2,5,6,7},
    {8,5,9,7,6,1,4,2,3},
    {4,2,6,8,5,3,7,9,1},
    {7,1,3,9,2,4,8,5,6},
    {9,6,1,5,3,7,2,8,4},
    {2,8,7,4,1,9,6,3,5},
    {3,4,5,2,8,6,1,7,9}

};

public static void main(String[] args) {
    if (rowColumnCheck() && boxCheck()) {
        System.out.println("Valid!");
    } else {
        System.out.println("Invalid!");
    }
}

private static boolean boxCheck() {
    for (int i = 0; i < sMatrix.length; i += 3) {
        for (int j = 0; j < sMatrix.length; j += 3) {
            boolean[] gridMatrix = new boolean[9];
            for (int k = i; k < 3 + i; k++) {
                for (int l = j; l < 3 + j; l++) {
                    int currentNumber = sMatrix[k][l];
                    if (currentNumber < 1 || currentNumber > 9) {
                        return false;
                    }
                    gridMatrix[currentNumber - 1] = true;
                }
            }
            for (boolean booleanValue : gridMatrix) {
                if (!booleanValue) {
                    return false;
                }
            }
        }
    }
    return true;
}

private static boolean rowColumnCheck() {
    for (int i = 0; i < 9; i++) {
        boolean[] rowArray = new boolean[9];
        boolean[] columnArray = new boolean[9];
        for (int j = 0; j < 9; j++) {
            int currentNumberRow = sMatrix[i][j];
            int currentNumberColumn = sMatrix[j][i];
            if ((currentNumberRow < 1 || currentNumberRow > 9) && (currentNumberColumn < 1 || currentNumberColumn > 9)) {
                return false;
            }
            rowArray[currentNumberRow - 1] = true;
            columnArray[currentNumberColumn - 1] = true;

        }
        for (boolean booleanValue : rowArray) {
            if (!booleanValue) {
                return false;
            }
        }
        for (boolean booleanValue : columnArray) {
            if (!booleanValue) {
                return false;
            }
        }
    }
    return true;
}

}

0

Решение, которое использует только одну итерацию массива. на протяжении всей итерации массива массив posRec будет иметь доступность каждого числа в строке / COL / GRID. если в posRec отсутствует бит, мы можем сказать, что судоку не является правильным.

#include <stdio.h>

#define ROW 0
#define COL 1
#define GRID 2
#define TRUE 1
#define FALSE 0


char sudoku_correct[9][9] ={{8,3,5,4,1,6,9,2,7},
                            {2,9,6,8,5,7,4,3,1},
                            {4,1,7,2,9,3,6,5,8},
                            {5,6,9,1,3,4,7,8,2},
                            {1,2,3,6,7,8,5,4,9},
                            {7,4,8,5,2,9,1,6,3},
                            {6,5,2,7,8,1,3,9,4},
                            {9,8,1,3,4,5,2,7,6},
                            {3,7,4,9,6,2,8,1,5}};

char sudoku_incorrect[9][9] ={{8,3,5,4,1,6,9,2,7},
                              {2,9,6,8,5,7,4,3,1},
                              {4,1,7,2,9,3,6,5,8},
                              {5,6,9,1,3,4,7,8,2},
                              {1,2,3,6,7,8,5,4,9},
                              {7,4,8,5,2,9,1,6,3},
                              {6,5,2,7,8,1,3,9,4},
                              {9,8,1,3,4,5,2,7,6},
                              {3,7,4,9,6,2,8,1,1}};



short posRec[9][3];

int isValid(char a[][9]) {
   int i, j, val, gIndex;

   for(i=0; i <9; i++){
      posRec[i][ROW] = 0;
      posRec[i][COL] = 0;
      posRec[i][GRID] = 0;
   }


   for(i=0; i<9; i++) {
      for(j=0; j<9; j++) {
         val=a[i][j]-1; //convert to 0-8 array index
         if((posRec[val][ROW]>>i) & 0x1)
            return FALSE;
         posRec[val][ROW] |= (0x1<<i);


         if((posRec[val][COL]>>j) & 0x1)
            return FALSE;
         posRec[val][COL] |= (0x1<<j);

         gIndex = (j/3) + ((i/3) * 3);
         if((posRec[val][GRID]>>gIndex) & 0x1)
            return FALSE;
         posRec[val][GRID] |= (0x1<<gIndex);

      }
   }

   for(i=0; i<9;i++){

      if(posRec[i][COL] != 0x1ff ||
         posRec[i][ROW] != 0x1ff ||
         posRec[i][GRID] != 0x1ff)
         return FALSE;
   }

   return TRUE;

}

int main(){

   printf("correct sudoku check = %s \n", isValid(sudoku_correct)?"CORRECT":"INCORRECT");
   printf("incorrect sudoku check = %s \n", isValid(sudoku_incorrect)?"CORRECT":"INCORRECT");
   return 0;
}
0