Basttercode monthly challenge 1 - 36. Validate Sudoku
comentada em 25/07/2023 17:03

bool isValidSudoku(char** board, int boardSize, int* boardColSize){

    int numberPresence[9];
    int i,j;
    int OriginI,OriginJ;
    int m,n;

    // Testa cada linha e marca quantas repetições tem cada numero. se tiver 2 ou mais retorna falso pois repetiu. pode ter 0 ou 1 que segue o jogo
    for(i=0;i<9;i++){
        memset(numberPresence,0,sizeof(int)*9);
        for(j=0;j<9;j++){
            if(board[i][j]!='.'){ // testa se tem numero, se não é só um ponto
                numberPresence[board[i][j]-'1']++;
                if(numberPresence[board[i][j]-'1']>1)
                    return false;
            }
        }
    }

    // mesma coisa pra coluna
    for(i=0;i<9;i++){
        memset(numberPresence,0,sizeof(int)*9);
        for(j=0;j<9;j++){
            if(board[j][i]!='.'){
                numberPresence[board[j][i]-'1']++;
                if(numberPresence[board[j][i]-'1']>1)
                    return false;        
            }
        }
    }

    //cada pedacito
    for(i=0;i<3;i++)
        for(j=0;j<3;j++){
            OriginI=3*i; //origem do pedacito em I
            OriginJ=3*j; //origem do pedacito em J 
            memset(numberPresence,0,sizeof(int)*9);
            for(m=0;m<3;m++)
                for(n=0;n<3;n++){ //a contagem dos numeros é repetida aqui, mas na minimatriz 3x3
                    if(board[OriginI+m][OriginJ+n]!='.'){
                        numberPresence[board[OriginI+m][OriginJ+n]-'1']++;
                        if(numberPresence[board[OriginI+m][OriginJ+n]-'1']>1)
                            return false;        
                        }                    
                }
        }

    return true;
}?

def check_sudoku_size(board: list, size) -> bool:
    # Verificar se o tamanho do board é válido
    check = False
    if len(board) == size:
        check = True
        for i in board:
            if len(i) != size:
                check = False
    return check

def pieces_of_sudoku(board: list, i, j) -> list:
    listax = board[i:i+3]
    listay = []
    for k in listax:
        listay.append(k[j:j+3])
    return listay

def transpose_sudoke(board: list) -> list:
    return list(map(list, zip(*board)))

def check_sudoku_rows_or_lines(board: list) -> bool:
    conjunto = set()
    validate = False
    val = []
    for i in board:
        lista = [int(a) for a in i if a!='.']
        conjunto = set(lista)
        #print(conjunto)
        #print(lista)
        if len(conjunto) == len(lista):
                validate = True
        val.append(validate)
    if False in val:
        return False
    else:
        return True
            
def small_sudoku(soduku_board: list) -> bool:
    validador = []
    for i in range(0,3):
        for j in range(0,3):
            flat_list = [item for sublist in pieces_of_sudoku(sudoku_board, i*3, j*3) for item in sublist]
            lista = [int(a) for a in flat_list if a!='.']
            conjunto = set(lista)
            if len(conjunto) == len(lista):
                print("Sudoku "+str(i*3)+" / "+str(j*3)+" small True")
                validador.append(True)
            else:
                print("Sudoku "+str(i*3)+" / "+str(j*3)+" small False")
                validador.append(False)
    if False in validador:
        return False
    else: 
        return True

def validador(sudoku: list) -> bool:
    val = []        
    if check_sudoku_size(sudoku, 9):
        if check_sudoku_rows_or_lines(sudoku) & check_sudoku_rows_or_lines(transpose_sudoke(sudoku)):
            print("Big Sudoku True")
            val.append(small_sudoku(sudoku))
        else:
            print("Big Sudoku False")
            val.append(small_sudoku(sudoku))

    if False in val:
        return False
    else: 
        return True
    
sudoku_board = [
    ["5", "3", ".", ".", "7", ".", ".", ".", "."],
    ["6", ".", ".", "1", "9", "5", ".", ".", "."],
    [".", "9", "8", ".", ".", ".", ".", "6", "."],
    ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
    ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
    ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
    [".", "6", ".", ".", ".", ".", "2", "8", "."],
    [".", ".", ".", "4", "1", "9", ".", ".", "5"],
    [".", ".", ".", ".", "8", ".", ".", "7", "9"]
]

print(validador(sudoku_board))

class Solution {
public:

/* O problema pede para checar um sudoku, retornando falso se houver repetição de números em alguma linha, coluna ou dentro de cada caixa (no sudoku, há nove caixas, 3 em cada linha/coluna). O input é um vetor de vetores, ou seja, uma matriz. No caso, uma matriz quadrada 9x9. Cada vetor linha/coluna contém apenas caracteres correspondentes aos dígitos de 1 a 9 ou o ponto ('.'). O problema não se importa se o sudoku é solucionável, mas apenas se, dentre os dígitos informados, ocorre alguma das repetições mencionadas. */

    bool isValidSudoku(vector<vector<char>>& board) {
        map<char, char> c; //mapa para verificar os dígitos nas colunas
        map<char, char> r; //mapa para verificar os dígitos nas linhas
        map<char, char> g; //mapa para verificar os dígitos nas caixas

        //passa por todos os elementos da matriz  uma vez
        for (int i = 0; i < 81; i++) {             
            char m = i % 9; //índice que varia rápido
            char n = i / 9; //indice que varia devagar

/* os índices abaixos são para as caixas. Com esses índices, cada variação de uma linha/coluna corresponde à passagem pelos 9 elementos de uma mesma caixa */

            char j = (m / 3) + (3*n % 9); 
            char k = (m % 3) + (3*n / 9)*3;

/* a cada 9 elementos, reseta os mapas, pois serão analisadas novas linhas, colunas e caixas */

            if (i % 9 == 0) {
                c.clear();
                r.clear();
                g.clear();
            }
            
/* como o índice que varia rápido corresponde às linhas e a coluna varia devagar, o condicional mapeia cada coluna. Apenas os valores diferentes do ponto, ou seja, os dígitos, são considerados. Na primeira ocorrência de cada dígito, o mapa assONcia ao dígito o valor 1. Na segunda ocorrência, houve repetição e o condicional retorna falso. */

            if (board[m][n] != '.') {
                if (c.count(board[m][n])) {
                    return false;
                } else {
                    c[board[m][n]] = 1;
                }
            }

/* mesma lógica aqui, mas o índice que varia rápido é o da coluna, então o mapa é dos dígitos de cada linha. */

            if (board[n][m] != '.') {                
                if (r.count(board[n][m])) {
                    return false;
                } else {
                    r[board[n][m]] = 1;
                }
            }

/* aqui o mapa corresponde a cada caixa. A lógica é a mesma. */

            if (board[j][k] != '.') {                
                if (g.count(board[j][k])) {
                    return false;
                } else {
                    g[board[j][k]] = 1;
                }
            }
        }

        //se não retornou falso no loop, é porque não há repetição
        return true;
    }
};?

class Solution {
    fun isValidSudoku(board: Array<CharArray>): Boolean {

        // my board is an instance of Sudoku class
        val myboard = Sudoku(board)
        // mycharlist receives several lists for checking if
        // line, column or square is false.
        var mycharlist = listOf<Char>()

        // loop from 1st to 9th...
        for (i in 0..8){
            // ... line
            mycharlist = myboard.getLine(i).sorted()
            //(sorted because during check number should always increase
            // and never repeat
            if (!listcheck(mycharlist)) return false

            // ... column
            mycharlist = myboard.getColumn(i).sorted()
            if (!listcheck(mycharlist)) return false

            // ... and square
            mycharlist = myboard.getSquare(i).sorted()
            if (!listcheck(mycharlist)) return false
        }

        return true
        
    }

    // this function receives a list of 9 sorted chars.
    // an empty char is represented by a ".", which when converted to int becomes 46.
    // a valid char is converted to a number that should always increase and never repeat.
    // if it repeats, return false
    fun listcheck(list: List<Char>): Boolean{
        // num stores the last known number
        var num = 0
        for (i in list.indices){
            // if empty (".") goes to next iteration
            if (list[i].toInt() == 46) continue
            // if a number repeats it's false
            if (num == list[i].toInt()) return false
            // stores present number in num
            else num = list[i].toInt()
        }
        return true
    }
}

// class for receiveing a Sudoku board and performing some board functions
class Sudoku(val board: Array<CharArray>) {

    // gets a line in a board
    fun getLine (line: Int): CharArray {
        return board[line]
    }

    // gets a column in a board
    fun getColumn (column: Int): CharArray{
        var columnArray = CharArray(9)
        // loop around every line in same column
        for (i in 0..8){
            columnArray[i] = board[i][column]
        }
        return columnArray
    }

    // gets a 3 by 3 square from a board
    fun getSquare (square: Int): CharArray{
        var squareArray = CharArray(9)
        // adopting that 3x3 squares are indexed from 0 to 8.
        // square 0 has starting line 0 and starting column 0
        // square 1 has starting line 0 and starting column 3
        // and so on until...
        // square 8 has starting line 6 and starting column 6
        // the following equations perform that calculation
        val startLine = (square / 3) * 3
        val startCol = (square % 3) * 3
        var k = 0
        // double loop from starting position up to the following 2 positions
        for (i in startLine..(startLine + 2)){
            for (j in startCol..(startCol + 2)){
                squareArray[k] = board[i][j]
                k++
            }
        }
        return squareArray
    }

}

postado por @Giovanni em 07/03/2023 21:49

vocês são feras!
desafio mensal, resolveram em um dia

tá na hora de partir para as perguntas de entrevista de FAANG hahaha

class Solution {
  bool areRowsValid(List<List<String>> board) {
      for (int row = 0; row < 9; row++)
          if (!isRowValid(board[row])) return false;
          
      return true;
  }
    
  bool isRowValid(List<String> row) {
      List<int> p = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ];
      for (int i = 0; i < 9; i++) {
          if (row[i] == ".") continue;
          if (p[int.parse(row[i])] == 1) return false;
          p[int.parse(row[i])] = 1;
      }
      return true;
  }
    
  bool areColumnsValid(List<List<String>> board) {
      for (int col = 0; col < 9; col++) {
          List<int> p = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];

          for (int row = 0; row < 9; row++) {
              if (board[row][col] == ".") continue;
              final numberToCheck = int.parse(board[row][col]);
              if (p[numberToCheck] == 1) return false;
              p[numberToCheck] = 1;
          }
      }
      
      return true;
  }
  bool isSubBoxValid(List<List<String>> board, int rowStart, int rowEnd, int colStart, int colEnd) {
      List<int> p = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
      for (int col = colStart; col < colEnd; col++) {
          for (int row = rowStart; row < rowEnd; row++) {
              if (board[row][col] == ".") continue;
              
              final numberToCheck = int.parse(board[row][col]);
              if (p[numberToCheck] == 1) return false;
              p[numberToCheck] = 1;
          }
      }     
      return true;
  }
    
 bool areSubBoxesValid(List<List<String>> board) {
     for (int subBoxRow = 0; subBoxRow < 3; subBoxRow++) {
         for (int subBoxCol = 0; subBoxCol < 3; subBoxCol++) {
            if (!isSubBoxValid(board, 
                               subBoxRow*3, 
                               (subBoxRow*3)+3, 
                               subBoxCol*3, 
                               (subBoxCol*3)+3
                              )) return false;
         }
     }
     return true;
  }    
    
  bool isValidSudoku(List<List<String>> board) {
    return 
        areRowsValid(board) &&
        areColumnsValid(board) && 
        areSubBoxesValid(board);
  }
}?

postado por @urbietorbi em 08/03/2023 19:50

Para quem tem tá usando class, não entendi muito bem o motivo. Alguém poderia explicar? Não fica muito mais fácil fazer procedural do que por classes?

class Solution {
    fun isValidSudoku(board: Array<CharArray>): Boolean {

        val myboard = Sudoku(board)
        var mycharlist = listOf<Char>()

        for (i in 0..8){

            mycharlist = myboard.getLine(i).sorted()
            if (!listcheck(mycharlist)) return false

            mycharlist = myboard.getColumn(i).sorted()
            if (!listcheck(mycharlist)) return false

            mycharlist = myboard.getSquare(i).sorted()
            if (!listcheck(mycharlist)) return false
        }
        return true
    }
}?

def inNumRange(l: list) -> list:
    r = [e for e in l if e in ('0','1','2','3','4','5','6','7','8','9','.')]
    if len(r) != 9:
        raise "Invalid input"
    return r

def haveDuplicates(l: list) -> bool:
    r = True
    l2 = [i for i in l if i != '.']
    if len(l2) == len(set(l2)):
        r = False
    return r

def getColumn(m: list[list], index: int) -> list:
    return [item[index] for item in m]

def getSquare(m: list[list], index: int) -> list:
    init = 0 # Default: index in [0,1,2]
    if index in [3,4,5]:
        init = 3
    if index in [6,7,8]:
        init = 6

    filter1 = 0 # Default: index in [0,3,6]
    filter2 = 3 # Default: index in [0,3,6]
    if index in [1,4,7]:
        filter1 = 3
        filter2 = 6
    if index in [2,5,8]:
        filter1 = 6
        filter2 = 9

    a = m[init][filter1:filter2]
    b = m[init+1][filter1:filter2]
    c = m[init+2][filter1:filter2]

    return [*a,*b,*c]

def main():
    for i in range(9):
        row = board[i]
        column = getColumn(board, i)
        square = getSquare(board, i)

        if haveDuplicates(inNumRange(row)): 
           return False
        if haveDuplicates(inNumRange(column)):
            return False
        if haveDuplicates(inNumRange(square)):
            return False
        
        return True

main()

class Solution {
public:      
    bool isValidSudoku(vector<vector<char>>& board) {
        vector<bool> g(410);  

        for (int i = 0; i < 81; i++) {
            char m = i % 9;
            char n = i / 9;
            
            int dig = board[m][n] - 48;            
            
            if (dig > 0) {
                int row = 10*(n) + dig;
                int col = 10*(m+9) + dig;
                int box = 100*(m/3) + 10*(n/3 + 18) + dig;
                
                if (g[row] == 1) return false;
                else g[row] = 1;
                if (g[col] == 1) return false;
                else g[col] = 1;
                if (g[box] == 1) return false;
                else g[box] = 1;
            }
        }
        return true;
    }
};?

from operator import itemgetter

def validate_values(values):
    values = [v for v in values if v != '.']
    return len(set(values)) == len(values)

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        for row in board:
            if not validate_values(row):
                return False

        transposed_board = zip(*board)
        for column in transposed_board:
            if not validate_values(column):
                return False

        for i in range(0, 9, 3):
            for j in range(0, 9, 3):
                box = map(itemgetter(slice(j, j+3)), board[i:i+3])
                if not validate_values([c for row in box for c in row]):
                    return False
        return True

postado por @oxe em 09/03/2023 19:41

Tentei encarar o problema de outra forma. Anteriormente fiz com maps, mas eu poderia "mapear" usando índices de vetores também.

Se eu fizer operações adequadas com os índices do board, posso gerar um número unicamente determinado para cada par linha/dígito, coluna/dígito e caixa/dígito.

E então usar esse número como índice de um novo vetor de booleans que liga quando o loop encontra o par, ou seja, quando, naquela linha, coluna ou caixa, se encontra o dígito em questão.

Se o vetor estiver ligado num dado índice, na segunda vez em que o programa for ligar o índice, houve repetição e a função retorna falso.

class Solution {
public:      
    bool isValidSudoku(vector<vector<char>>&amp; board) {
        vector<bool> g(410);  

        for (int i = 0; i < 81; i++) {
            char m = i % 9;
            char n = i / 9;
            
            int dig = board[m][n] - 48;            
            
            if (dig > 0) {
                int row = 10*(n) + dig;
                int col = 10*(m+9) + dig;
                int box = 100*(m/3) + 10*(n/3 + 18) + dig;
                
                if (g[row] == 1) return false;
                else g[row] = 1;
                if (g[col] == 1) return false;
                else g[col] = 1;
                if (g[box] == 1) return false;
                else g[box] = 1;
            }
        }
        return true;
    }
};?

class Solution {
public:      
  bool isValidSudoku(vector<vector<char>>& board) {
    bitset<283> chk; 

    for (int i = 0; i < 81; i++) {
      char m = i % 9;
      char n = i / 9;            
      char d = board[m][n] - 49;           
            
      if (d >= 0) {
        int row = 9*m + d;
        int col = 9*(n+9) + d;
        int box = 27*(m/3) + 9*(n/3) + 162 + d;
                
        if (chk[row]) return false;
        else chk[row] = 1;
        if (chk[col]) return false;
        else chk[col] = 1;
        if (chk[box]) return false;
        else chk[box] = 1;                
      }
            
      if ((80 - i) > i) {           
        m = (80 - i) % 9;
        n = (80 - i) / 9;
        d = board[m][n] - 49;
            
        if (d >= 0) {
          int row = 9*m + d;
          int col = 9*(n+9) + d;
          int box = 27*(m/3) + 9*(n/3) + 162 + d;
                
          if (chk[row]) return false;
          else chk[row] = 1;
          if (chk[col]) return false;
          else chk[col] = 1;
          if (chk[box]) return false;
          else chk[box] = 1;                
        }
      } else break;
    }
  return true;
}
};?

class Solution:
    def isValidSudoku(self, board: list[list[str]]) -> bool:
        rows, cols = board[:], [list(c) for c in list(zip(*board))]

        def boxes():
            boxes, indexs = [], [0, 3, 6]
            for i in indexs:
                for j in indexs:
                    box = []
                    for k in range(3): box += board[i + k][j:j + 3]
                    boxes += [box]
            return boxes
                
        def check(matrix):
            for row in matrix:
                while "." in row: row.remove(".")
                if len(row) != len(set(row)): return False

        invalid = False in list(map(check,[rows, cols, boxes()]))
        return not invalid

defmodule Solution do
  @nums [?1, ?2, ?3, ?4, ?5, ?6, ?7, ?8, ?9]
  @ranges [0..2, 3..5, 6..8]

  @spec is_valid_sudoku(board :: [[char]]) :: boolean
  def is_valid_sudoku(board) do
    lines? = board |> Enum.all?(&valid_block?/1) 
    cols? = board |> transpose() |> Enum.all?(&valid_block?/1) 
    blocks? = board |> make_blocks() |> Enum.all?(&valid_block?/1) 

    lines? and cols? and blocks?
  end

  defp transpose(board), do: Enum.zip_with(board, & &1)

  defp valid_block?(block) do
    nums = Enum.filter(block, &(&1 in @nums)) 
    uniq_nums = Enum.uniq(nums) 

    Enum.count(nums) == Enum.count(uniq_nums)
  end
  defp make_blocks(board) do
    for r1 <- @ranges, r2 <- @ranges do
      for idx1 <- r1, idx2 <- r2 do
        board |> Enum.at(idx1) |> Enum.at(idx2)
      end
    end
  end
end

postado por @oxe em 14/03/2023 12:47

Boa tarde, galera.

Eu tenho estudado por tutoriais e outros materiais gratuitos na net, mas acho que ficam vários buracos no conhecimento. Muitos desses desafios exigem algum conceito que eu não li nesses tutoriais, por exemplo. 

Aí eu tava pensando em seguir algum material mais bem estruturado, que cubra pelo menos todos os conceitos básicos e me indique o caminho para me aprofundar.

Fui pesquisar e encontrei recomendações deste livro aqui. Aparentemente foi escrito pelo cara que criou o C++ e é voltado para iniciantes. 

Programming: Principles and Practice Using C++ (English Edition)
https://a.co/d/1ZA2qmA

Vocês conhecem o livro? É bom mesmo? 

Outra coisa, ele é de 2014. Eu perco muita coisa pegando um livro mais antigo, mesmo considerando que é mais voltado para iniciante? 

from math import floor

sudoku_board = [
    ["5", "3", ".", ".", "7", ".", ".", ".", "."],
    ["6", ".", ".", "1", "9", "5", ".", ".", "."],
    [".", "9", "8", ".", ".", ".", ".", "6", "."],
    ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
    ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
    ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
    [".", "6", ".", ".", ".", ".", "2", "8", "."],
    [".", ".", ".", "4", "1", "9", ".", ".", "5"],
    [".", ".", ".", ".", "8", ".", ".", "7", "9"]
]

def validar_conjunto(conjunto):
  valores = []
  repetidos = set()

  for dado in conjunto:
    if dado not in valores:
      valores.append(dado)
    else:
      repetidos.add(dado)
  
  boleano = False

  if repetidos == set():
    boleano = True
    #print(boleano)
  if repetidos == {'.'}:
    boleano = True
    #print(boleano)
  #print(repetidos,boleano)
  return boleano

linhas = []
for linha in range(9):
  conjunto = sudoku_board[linha]
  print(conjunto)
  boleano = validar_conjunto(conjunto)
  linhas.append(boleano)
print("linhas =", linhas)
print("...")

colunas = []
for coluna in range(9):
  conjunto = []
  for i in range(9):
    conjunto.append(sudoku_board[i][coluna])
  print(conjunto)
  boleano = validar_conjunto(conjunto)
  colunas.append(boleano)
print("colunas =", colunas)
print("...")

quadradoes = []
for i in range(3):
  for j in range(3):
    conjunto = []
    for k in range(9):
      for l in range(9):
        if floor(k/3) == i and floor(l/3) == j:
          conjunto.append(sudoku_board[k][l])
    print(conjunto)
    boleano = validar_conjunto(conjunto)
    quadradoes.append(boleano)
print("quadradoes =",quadradoes)
print("...")

#TABELA VERDADE
tv = [True,True,True,True,True,True,True,True,True]
print("TABELA VERDADE =",tv)
print("...")

if linhas == colunas == quadradoes == tv:
  output = True
  print("Esse sudoku é válido e não possui repetições inapropriadas")
else:
  output = False
  print("Esse sudoku é inválido devido possuir repetições inapropriadas")
print("...")
print(output)

postado por @laotzu em 25/03/2023 20:12

shadow_walker achei esse seu código especialmente sintético. Qual é essa linguagem?

postado por @FlyCavok em 25/03/2023 22:03

laotzu o código dele é Python, não?

É que ele é fera neném

Aliás, parabéns por entrar no desafio!

postado por @laotzu em 25/03/2023 22:39

FlyCavok pensei que fosse python.
Só não consigo "falar e nem entender" nesse nível.

Fera-neném de alto nível!

Obrigado pela força.

postado por @FlyCavok em 08/03/2023 19:27

(...)
Obs: quem tiver com coragem e curiosidade, pode tentar resolver o exercício irmão desse, que é o Sudoku Solver.

O Sudoku Solver recebe um sudoku não totalmente preenchido e o retorna preenchido. É de nível hard.  LeetCode - The World's Leading Online Programming Learning Platform
Se alguém tiver curiosidade posso mostrar como resolver. Eu o resolvi há algum tempo.