Valid Sudoku-Clean and dirty solution.
A while ago I attempted to solve this leetcode challenge
https://leetcode.com/problems/valid-sudoku/description/
For my first try I came up with this
bool checkRow(int rowNo, int colNo, char** board){
for( int i = 0; i < 9; i++){
if(board[colNo][rowNo] == board[colNo][i]){
if(rowNo == i && colNo == colNo ) continue;
return false;
}
}
return true;
}
bool checkCol(int rowNo, int colNo, char** board){
for(int i = 0; i < 9; i++){
if(board[colNo][rowNo] == board[i][rowNo]){
if(rowNo == rowNo && colNo == i) continue;
return false;
}
}
return true;
}
bool checkBox(int rowNo, int colNo, char** board){
int i, j;
printf("from checkBox, %d, %d\n", colNo, rowNo);
if((rowNo >= 0 && rowNo <= 2) && (colNo >= 0 && colNo <= 2)){
for(i = 0; i < 3; i++){
for(j = 0; j < 3; j++){
if(board[colNo][rowNo] == board[i][j]){
if(colNo == i && rowNo == j ) continue;
printf("0 returned false");
// printf("%c, %c, colNo %d, i %d, rowNo %d, j %d\n", board[colNo][rowNo], board[i][j],colNo, i, rowNo, j);
// printf("returned false\n");
return false;
}
}
}
return true;
}
if((rowNo >= 3 && rowNo <= 5) && (colNo >=0 && colNo <= 2)){
for(i = 0; i < 3; i++){
for(j = 3; j < 6; j++){
if(board[colNo][rowNo] == board[i][j]){
if(colNo == i && rowNo == j )continue;
printf("1 returned false");
// printf("%c, %c, colNo %d, i %d, rowNo %d, j %d\n", board[colNo][rowNo], board[i][j],colNo, i, rowNo, j);
// printf("returned false\n");
return false;
}
}
}
return true;
}
if((rowNo >= 6 && rowNo <= 8) && (colNo >= 0 && colNo <= 2)){
for(i = 0; i < 3; i++){
for(j = 6; j < 9; j++){
if(board[colNo][rowNo] == board[i][j]){
if(colNo == i && rowNo == j )continue;
printf("2 returned false");
return false;
}
}
}
return true;
}
if((rowNo >= 0 && rowNo <= 2) && (colNo >= 3 && colNo <= 5)){
for(i = 3; i < 6; i++){
for(j = 0; j < 3; j++){
if(board[colNo][rowNo] == board[i][j]){
if(colNo == i && rowNo == j )continue;
printf("3 returned false");
return false;
}
}
}
return true;
}
if((rowNo >= 3 && rowNo <= 5) && (colNo >= 3 && colNo <= 5)){
for(i = 3; i < 6; i++){
for(j = 3; j < 6; j++){
if(board[colNo][rowNo] == board[i][j]){
if(colNo == i && rowNo == j )continue;
printf("4 returned false");
return false;
}
}
}
return true;
}
if((rowNo >= 6 && rowNo <= 8) && (colNo >= 3 && colNo <= 5)){
for(i = 3; i < 6; i++){
for(j = 6; j < 9; j++){
if(board[colNo][rowNo] == board[i][j]){
if(colNo == i && rowNo == j )continue;
printf("5 returned false");
return false;
}
}
}
return true;
}
if((rowNo >= 0 && rowNo <= 2) && (colNo >= 6 && colNo <= 8)){
for(i = 6; i < 9; i++){
for(j = 0; j < 3; j++){
if(board[colNo][rowNo] == board[i][j]){
if(colNo == i && rowNo == j )continue;
printf("6 returned false");
return false;
}
}
}
return true;
}
if((rowNo >= 3 && rowNo <= 5) && (colNo >= 6 && colNo <= 8)){
for(i = 6; i < 9; i++){
for(j = 3; j < 6; j++){
if(board[colNo][rowNo] == board[i][j]){
if(colNo == i && rowNo == j )continue;
printf("7 returned false");
return false;
}
}
}
return true;
}
if((rowNo >= 6 && rowNo <= 8) && (colNo >= 6 && colNo <= 8)){
for(i = 6; i < 9; i++){
for(j = 6; j < 9; j++){
if(board[colNo][rowNo] == board[i][j]){
if(colNo == i && rowNo == j )continue;
printf("8 returned false");
return false;
}
}
}
return true;
}
return true;
}
bool isValidSudoku(char** board, int boardSize, int* boardColSize) {
int colNo = 0;
int rowNo = 0;
// for(int i = 0; i < 8; i++){
// printf("%c", board[1][i]);
// }
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++){
if(board[i][j] == '.') continue;
printf("%d, %d\n", i, j);
if(!checkRow(j, i, board)){
printf("from checkRow" );
return false;
}
if(!checkCol(j, i, board)){
printf("from checkCol");
return false;
}
if(!checkBox(j, i, board)){
printf("from checkBox");
return false;
}
}
}
return true;
}Oh boy, that was something, then I posted it on Reddit (Rookie Mistake đ). letâs just say they meant well.
This were some of the responses
First immediate WTF: why are you comparing colNo to itself in checkRow and rowNo to itself in checkCol? That looks like some copy/paste/modify without looking sort of thing. :)
Beyond that, youâre checking things redundantly. You have 9 rows, 9 columns and 9 boxes, but youâre checking them each 81 times. For example, once youâve checked a box for one of its values, you donât have to check the box again for another. Just pick the top left corner of each box as opposed to iterating over every square in a box.
1. â First thing I would do is clean up the code a bit and make it shorter. The checkBox function only needs one loop in it, not nine.
2. â Next, the char** can be flattened to char*. One array, 81 elements.
3. â Next, you can use a bitmask to check which numbers appear in each group. You can iterate once over a group, and at the end, check that the bitmask is equal to 0x1ff (nine ones). Each bit records the presence of a different digit.
As already recommended by others, use bitmasks, remove redundancy and try to use a little more generic code. Here is such an implementation : https://onlinegdb.com/thgDDtXSx
Pretty helpful
So now I attempted it again but I used c hash, why? Life is short.
And thanks to this video for the wonderful explanation
It was really helpful
using System;
using System.Collections.Generic;
public class Solution {
public bool IsValidSudoku(char[][] board) {
HashSet<string> seen = new HashSet<string>();
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++){
char num = board[i][j];
if(num != â.â){
if(!seen.Add(num + "at row" + i) || !seen.Add(num + "at col" + j) || !seen.Add(num + "at square" + i/3 + "-" + j/3)){
return false;
}
}
}
}
return true;
}
}Yeah, that was the quick and clean solution. The other time I was looping through unnecessarily, using a hashmap in c would also be more efficient than what I was doing. So the code could be rewritten to fit that better.
Conclusion
Give a solution, go through other peopleâs solutions as well, and compare or rewrite to get more efficient solutions.
