Time for another home assignment! :P
Given a solved sudoku board, the aim is to check whether it is a valid solution or not. The program pasted below will do the same. In fact, it prints out ALL the offending rows, columns and blocks (if the solution is not valid). The idea is simple, if a row/column/block has all its elements to be unique, then the sum of all it's elements will be (N*(N+1))/2, where NxN is the size of the sudoku board.
#include <stdio.h> void isCorrect(int** grid, int N, int sqrootN) { int sum = (N * (N + 1)) >> 1; // all rows for(int i=0;i<N;i++) { int actual = 0; for(int j=0;j<N;j++) { actual += grid[i][j]; } if(actual != sum) { printf("Row '%d' is incorrect!\n", i+1); } } // all columns for(int i=0;i<N;i++) { int actual = 0; for(int j=0;j<N;j++) { actual += grid[j][i]; } if(actual != sum) { printf("Column '%d' is incorrect!\n", i+1); } } // all blocks for(int i=0;i<N;i+=sqrootN) { for(int j=0;j<N;j+=sqrootN) { int actual = 0; for(int a=0;a<sqrootN;a++) { for(int b=0;b<sqrootN;b++) { actual += grid[i+a][j+b]; } } if(actual != sum) { printf("Block starting at '%d,%d' is incorrect!\n", i+1,j+1); } } } } int main(int argc, char** argv) { if(argc == 2) { FILE* fp = fopen(argv[1], "r"); if(fp == NULL) { fprintf(stderr, "Failed to open '%s' for reading!\n", argv[1]); return 1; } int N, sqrootN; int** grid; fscanf(fp, "%d", &N); fscanf(fp, "%d", &sqrootN); grid = new int* [N]; for(int i=0;i<N;i++) { grid[i] = new int [N]; for(int j=0;j<N;j++) { fscanf(fp, "%d", &(grid[i][j])); } } isCorrect(grid, N, sqrootN); for(int i=0;i<N;i++) { delete grid[i]; } delete grid; fclose(fp); } else { fprintf(stderr, "USAGE: %s <file>\n", argv[0]); return 1; } return 0; }
How to compile?
(Assuming the above program is saved in the file sudokuChecker.cpp)
g++ -o checker sudokuChecker.cpp
How to run?
./checker <file>
<file> = the file containing the sudoku board
No comments:
Post a Comment