The Sudoku Problem

Sudoku is a delightful puzzle that appeals to people from all walks of life today. It not only sharpens the intellect but also enhances focus. Originating from the Japanese phrase "Suuji wa dokushin ni Kagiru," which means "numbers must be single," Sudoku has become immensely popular, spreading from Asia to Europe and North America.

The objective of the game is to fill a grid divided into nine equal squares, each containing nine smaller squares, with numbers from 1 to 9 in such a way that each number appears only once. Additionally, each number must be used only once in every row and column.

Sudoku has become so popular that there are even toilet papers designed with Sudoku puzzles for those who wish to play while in the restroom. For those who find the standard 9x9 matrix too limiting, there are even larger 16x16 matrices available. There are even games prepared with complex matrices instead of regular ones (refer to picture-3).

As the situation has become so complex, we decided to utilize computer power to solve it. A Sudoku puzzle that first appears to be quite challenging to first graders in the sixth month of the Olympiad can, upon closer inspection, be understood to be a very simple question. A computer can solve a standard Sudoku in less than a second. Of course, a computer is not as intelligent as a human. However, it can quickly test all possibilities and display the correct one on the screen. For those curious about how all this is explained to a computer, we have written the C code below that can solve the Sudoku puzzle.

SUDOKU

A 9x9 board is divided into 3x3 sections as shown below. Place numbers from 1 to 9 in these 3x3 squares using each number only once. Your placement must ensure that in all 3x3 boxes, as well as in all rows and columns, numbers from 1 to 9 are used exactly once. This game is called Sudoku.

Input

- Will be read from sudokuin.txt file.

- The first line will consist of an N number. (0<=N<=81) N indicates how many cells are filled.

- Each of the following N lines will contain 3 numbers: The first two are the coordinates of the square with a number, and the third is the number placed in that square.

Output

- Will be written to sudokuout.txt file.

- A 9x9 board will be printed.

- This board is the solution to the Sudoku game. Any solution is acceptable.

- If there is no solution, it must be indicated with the message "impossible" (Do not write anything else...).

Solution Code

In brief, the main() function, as implied by its name, is the main function. The oku() function reads cells that are already filled. The yap() function recursively tries numbers in empty cells. The yaz() function, as its name suggests, prints the filled Sudoku board to sudokuout.txt file. If no solution is found, it prints "impossible"...

Although the code is briefly explained above, it's a fact that someone who doesn't know C would find it impossible to understand this code. A person unfamiliar with C might even think that such a code needs to be memorized. However, someone who knows C would realize that there's no need for memorization, as it is an easily understandable code. This is precisely where the computer Olympiad comes into play...

The Olympiad first teaches the logic of how a computer works. Even though a computer processor is much less advanced than the human brain, it can concentrate solely on that task, making its efficiency many times greater than that of the human brain. You explain something to the computer, using different languages like C, C++, Java, and it processes according to the logic you described. Of course, the first thing you learn in the Olympiad is a programming language.

Then, the Olympiad instills a strong work ethic in participants. I coded the above code non-stop for four and a half hours when I was in the first year of high school. Before that, I wasn't someone who could work uninterrupted even for two hours…

Lastly, the Olympiad develops the ability to think in multiple dimensions. Did you know, by the way, that there are more than five solutions to the Sudoku puzzle?

#include<stdio.h>

#include<stdlib.h>

#define MAX 9

int bulundu, n, x;

int A[MAX][MAX], SATIR[MAX][MAX], SUTUN[MAX][MAX], KUTU[MAX][MAX];

void doldur(int i,int j,int sayi)

{

      SATIR[i][sayi-1]=SUTUN[j][sayi-1]=KUTU[j/3+(i/3)*3][sayi-1]=1;

      A[i][j]=sayi;

      x++;

}

void bosalt(int i,int j,int sayi)

{

      SATIR[i][sayi-1]=SUTUN[j][sayi-1]=KUTU[j/3+(i/3)*3][sayi-1]=0;

      A[i][j]=0;

      x--;

}

void oku()

{

      FILE *r=fopen("sudokuin.txt","r");

      fscanf(r," %d",&n);

      int i,j,k,sayi;

      for(k=0;k<n;k++)

      {

            fscanf(r," %d %d %d",&i,&j,&sayi);

            i--; j--;

            doldur(i,j,sayi);

      }

}

int uygunmu(int i,int j,int sayi)

{

      return !(SATIR[i][sayi-1] || SUTUN[j][sayi-1] || KUTU[j/3+(i/3)*3][sayi-1]);

}

void yaz()

{

      int i,j;

      FILE *wrt=fopen("sudokuout.txt","w");

      if(!bulundu){fprintf(wrt,"imkansiz\n"); return;}

      for(i=0;i<MAX;i++)

      {

            for(j=0;j<MAX;j++)

                  fprintf(wrt,"%-2d",A[i][j]);

            fprintf(wrt,"\n");

      }

      fclose(wrt);

}

void yap(int i)

{

      if(x==81)

      {

            bulundu=1;

            yaz();

            exit(0);

      }

      int sat,sut,s;

      for(sat=i;sat<MAX;sat++)

      {

            for(sut=0;sut<MAX;sut++)

                  if(!A[sat][sut])

                goto cik;

      }

cik:

      for(s=1;s<=MAX;s++)

            if(uygunmu(sat,sut,s))

            {

                  doldur(sat,sut,s);

                  yap(sat);

                  bosalt(sat,sut,s);

            }

}

int main()

{

      oku();

      yap(0);

      return 0;

}