Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- typedef struct _Array
- {
- short *arr;
- unsigned short size;
- } Array;
- #define EMPTY_SQUARE -1
- #define NOT_FINISH -2
- #define FINISH_SUCCESS 0
- #define FINISH_FAILURE -3
- #define BOARD_SIZE 9
- #define FILLED 1
- #define FAIL 0
- typedef int bool;
- #define true 1
- #define false 0
- short* bucketsort(short sudokuBoard[][9], int row, int col, int size, unsigned short*arrSize);
- Array ***PossibleDigits(short sudokuBoard[][9]);
- int FillBoard(short board[][9], Array ***possibilities);
- int OneStage(short board[][9], Array ***possibilities, int *x, int *y);
- void UpdatePossibilities(short board[][9], Array***possibilities, int row, int col, int squareValue);
- void UpdateSquarePossibilities(Array***possibilities, int row, int col, unsigned short arrSize, int squareValue);
- bool SearchForDuplications(short board[][9], int row, int col, int SquareValue);
- void printPossibilities(Array***possibilities, int x, int y);
- void sudokoPrintBoard(short board[][9]);
- void main()
- {
- short board[9][9] =
- { 5, -1, 4, -1, 7, -1, -1, 1, -1,
- 6, -1, 2, 1, -1, -1, 3, -1, -1,
- 1, -1, 8, -1, 4, -1, -1, 6, -1,
- -1, 5, -1, -1, 6, -1, -1, 2, -1,
- -1, 2, -1, 8, -1, 3, -1, -1, -1,
- -1, -1, -1, -1, -1, 4, -1, 5, 6,
- -1, 6, 1, 5, 3, 7, 2, 8, 4,
- -1, 8, 7, -1, 1, 9, -1, 3, -1,
- -1, -1, -1, 2, 8, -1, -1, -1, 9 };
- Array*** possible_solutions;
- printf("Initial board\n");
- sudokoPrintBoard(board);
- printf("Press enter to start playing...\n");
- getchar();
- possible_solutions = PossibleDigits(board);
- if (FillBoard(board, possible_solutions) == -1)
- printf("User's selections led to duplications\n");
- else
- {
- sudokoPrintBoard(board);
- printf("Board filled successfully\n");
- }
- }
- void sudokoPrintBoard(short board[][9])
- {
- int i, j;
- for (i = 0; i < BOARD_SIZE; i++)
- {
- for (j = 0; j < BOARD_SIZE; j++)
- {
- if (board[i][j] == -1)
- printf("%d ", board[i][j]);
- else
- printf(" %d ", board[i][j]);
- }
- printf("\n");
- }
- }
- int FillBoard(short board[][9], Array ***possibilities)
- {
- int status;
- int x, y;
- int option;
- int squareValue;
- status = OneStage(board, possibilities, &x, &y);
- while (status == NOT_FINISH)
- {
- printPossibilities(possibilities, x, y);
- scanf("%d", &option);
- squareValue = possibilities[x][y]->arr[option - 1];
- board[x][y] = squareValue;
- UpdatePossibilities(board, possibilities, x, y, squareValue);
- status = OneStage(board, possibilities, &x, &y);
- }
- if (status == FINISH_SUCCESS)
- return(FILLED);
- else
- return(FAIL);
- }
- void printPossibilities(Array***possibilities,int x,int y)
- {
- int i;
- for (i = 0; i < possibilities[x][y]->size; i++)
- printf("%d. %d\n", i+1, possibilities[x][y]->arr[i]);
- return;
- }
- int OneStage(short board[][9], Array ***possibilities, int *x, int *y)
- {
- bool full = true;
- bool dupFound = false;
- int i, j;
- int xIndex, yIndex;
- int squareValue;
- unsigned short minPossibilities = 9;
- for (i = 0; i < BOARD_SIZE; i++)
- {
- for (j = 0; j < BOARD_SIZE; j++)
- {
- if (board[i][j] == EMPTY_SQUARE)
- {
- if (possibilities[i][j]->size == 1)
- {
- squareValue = possibilities[i][j]->arr[0];
- board[i][j] = squareValue;
- dupFound = SearchForDuplications(board, i, j, squareValue);
- if (dupFound == true)
- return(FINISH_FAILURE);
- free(possibilities[i][j]->arr);
- free(possibilities[i][j]);
- possibilities[i][j] = NULL;
- UpdatePossibilities(board, possibilities, i, j, squareValue);
- }
- else
- {
- full = false;
- if (minPossibilities > possibilities[i][j]->size)
- {
- minPossibilities = possibilities[i][j]->size;
- xIndex = i;
- yIndex = j;
- }
- }
- }
- }
- }
- if (full == false)
- {
- *x = xIndex;
- *y = yIndex;
- return(NOT_FINISH);
- }
- else
- return(FINISH_SUCCESS);
- }
- bool SearchForDuplications(short board[][9], int row, int col, int SquareValue)
- {
- int count = 0;
- int i, j;
- int rowBlock;
- int colBlock;
- for (i = 0; i < BOARD_SIZE; i++)
- {
- if (board[row][i] == SquareValue)
- count++;
- }
- if (count>1)
- return(true);
- count = 0;
- for (i = 0; i < BOARD_SIZE; i++)
- {
- if (board[i][col] == SquareValue)
- count++;
- }
- if (count>1)
- return(true);
- count = 0;
- rowBlock = row / 3;
- colBlock = col / 3;
- for (i = 3 * rowBlock; i < 3 * rowBlock + 3; i++)
- {
- for (j = 3 * colBlock; j < 3 * colBlock + 3; j++)
- {
- if (board[i][j] == SquareValue)
- count++;
- }
- }
- if (count>1)
- return(true);
- else
- return(false);
- }
- void UpdatePossibilities(short board[][9], Array***possibilities, int row, int col, int squareValue)
- {
- int i;
- int j;
- int rowBlock;
- int colBlock;
- for (i = 0; i < BOARD_SIZE; i++)
- {
- if (board[row][i] == EMPTY_SQUARE)
- UpdateSquarePossibilities(possibilities, row, i, possibilities[row][i]->size, squareValue);
- }
- for (i = 0; i < BOARD_SIZE; i++)
- {
- if (board[i][col] == EMPTY_SQUARE)
- UpdateSquarePossibilities(possibilities, i, col, possibilities[row][i]->size, squareValue);
- }
- rowBlock = row / 3;
- colBlock = col / 3;
- for (i = 3 * rowBlock; i < 3 * rowBlock + 3; i++)
- {
- for (j = 3 * colBlock; j < 3 * colBlock + 3; j++)
- {
- if (board[i][j] == EMPTY_SQUARE)
- UpdateSquarePossibilities(possibilities, i, j, possibilities[row][i]->size, squareValue);
- }
- }
- return;
- }
- void UpdateSquarePossibilities(Array***possibilities, int row, int col, unsigned short arrSize, int squareValue)
- {
- unsigned short i;
- unsigned short newSize;
- int write = 0;
- short* updatedArr;
- bool found = false;
- for (i = 0; i < arrSize && found == false; i++)
- {
- if (possibilities[row][col]->arr[i] == squareValue)
- {
- found = true;
- }
- }
- if (found == false)
- return;
- newSize = arrSize - 1;
- updatedArr = (short*)malloc(newSize*sizeof(short));
- for (i = 0; i < arrSize; i++)
- {
- if (possibilities[row][col]->arr[i] != squareValue)
- {
- updatedArr[write] = possibilities[row][col]->arr[i];
- write++;
- }
- }
- free(possibilities[row][col]->arr);
- possibilities[row][col]->arr = updatedArr;
- possibilities[row][col]->size = newSize;
- return;
- }
- Array ***PossibleDigits(short sudokuBoard[][9])
- {
- Array*** newBoard;
- int i;
- int j;
- newBoard = (Array***)malloc(BOARD_SIZE*(sizeof(Array**)));
- if (!newBoard) //if allocation faild
- {
- //allocation faild
- }
- for (i = 0; i < BOARD_SIZE; i++)
- {
- newBoard[i]= (Array**)malloc(BOARD_SIZE*(sizeof(Array*)));
- if (!newBoard) //if allocation faild
- {
- //allocation faild
- }
- }
- for (i = 0; i<9; i++)
- {
- for (j = 0; j<9; j++)
- {
- newBoard[i][j] = (Array*)malloc(sizeof(Array)); //allocation every cell to Array struct
- if (!newBoard[i][j]) //if allocation faild
- {
- //exit
- }
- }
- }
- for (i = 0; i <BOARD_SIZE; i++)
- {
- for (j = 0; i < BOARD_SIZE; i++)
- {
- if (sudokuBoard[i][j] == EMPTY_SQUARE)
- newBoard[i][j]->arr = bucketsort(sudokuBoard, i, j, BOARD_SIZE, &newBoard[i][j]->size);
- else
- newBoard[i][j]->arr = NULL;
- }
- }
- return(newBoard);
- }
- short* bucketsort(short sudokuBoard[][9], int row, int col, int size, unsigned short*arrSize)
- {
- int i, j; //index for
- int count[10]; //new array
- unsigned short sizeCount = 0;
- int squareValue;
- int sudokuBlockSize = 3;
- short *arr;
- int write = 0;
- int rowBlock;
- int colBlock;
- for (i = 0; i < size; i++)
- count[i] = 0;
- for (i = 0; i < size; i++)
- {
- squareValue = sudokuBoard[i][col];
- if (squareValue != EMPTY_SQUARE)
- count[sudokuBoard[i][col]]++;
- }
- for (i = 0; i < size; i++)
- {
- squareValue = sudokuBoard[row][i];
- if (squareValue != EMPTY_SQUARE)
- count[sudokuBoard[row][i]]++;
- }
- rowBlock = row / 3;
- colBlock = col / 3;
- for (i = 3 * rowBlock; i < 3 * rowBlock + 3; i++)
- {
- for (j = 3 * colBlock; j < 3 * colBlock + 3; j++)
- {
- squareValue = sudokuBoard[i][j];
- if (squareValue != EMPTY_SQUARE)
- count[sudokuBoard[i][j]]++;
- }
- }
- for (i = 1; i <= size; i++)
- if (count[i] == 0)
- sizeCount++;
- *arrSize = sizeCount;
- arr = (short*)malloc(sizeCount*sizeof(short));
- for (i = 1; i <= size; i++)
- {
- if (count[i] == 0)
- {
- arr[write] = i;
- write++;
- }
- }
- return(arr);
- }
- int countDigits(int num) /*This function count the amount of digits in 'num'*/
- {
- int count;
- count = 0;
- while (num > 0)
- {
- num = num / 10;
- count++;
- }
- return(count);
- }
- void printMultTable(int maxMult) /*This function prints the Multiplication Table at the size of maxMult x maxMult*/
- {
- int i; /*loop index*/
- int j; /*loop index*/
- int maxcount;/*holds the maximum amount of digits a number can reach in the current mult table*/
- int count; /*Holds the current amount of digits*/
- int nextcount; /*Holds the amount of digits of the next number*/
- maxcount = countDigits(maxMult); /*Call to function*/
- for (i = 1; i <= maxMult; i++) /*Main loop*/
- {
- printf("%*d", maxcount, i);
- for (j = 2; j <= maxMult; j++)
- {
- count = countDigits(i*j);
- nextcount = countDigits((maxMult)*j);
- if (count < nextcount)
- {
- printf("%*d", nextcount + 1, i*j);
- }
- else
- printf("%*d", count + 1, i*j);
- }
- printf("\n");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement