CodeWalrus

Development => Calculators => Calculator News, Coding, Help & Talk => Topic started by: semiprocoder on October 25, 2015, 12:43:39 am

Title: Sudoku Random Level Generator
Post by: semiprocoder on October 25, 2015, 12:43:39 am
Hi :). I am currently working on sudoku for the ti nspire, but I only have 2 levels for it right now, and don't want to post it until at least a good bit of levels have been made. I want to use a custom level generator,which outputs a file, the contents of which I will copy and past into my lua script for the game, or it that I started writing in c(well c++ technically, as I use the new and delete keywords cause im lazy), but I have little clue as to how to generate random sudoku generators. My first attempt at writing a complete sudoku board(withiout all the numbers missing in a puzzle, and that is something else I need help with) compeletely doesn't work, and I still am not sure as to how to improve it. I know why it doesn't work, but I have zero idea as to how to do it better. Anyways, here is my starting code for the generator. I am still going to try to fix it myself, but it would be great if someone could help me create a legit sudoku board generator.

Here is my code, which is horrible(and isnt random yet, it just uses the first value it can), but anyways:


#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
#include <stdlib.h>
const char* fileLoc = "C:\\Users\\Andrew\\vs\\sudoku\\easyLevels.txt";
FILE *myfile;
int board[9][9] = { { 0,0,0,0,0,0,0,0,0 },{ 0,0,0,0,0,0,0,0,0 },{ 0,0,0,0,0,0,0,0,0 },{ 0,0,0,0,0,0,0,0,0 },{ 0,0,0,0,0,0,0,0,0 },{ 0,0,0,0,0,0,0,0,0 },{ 0,0,0,0,0,0,0,0,0 },{ 0,0,0,0,0,0,0,0,0 },{ 0,0,0,0,0,0,0,0,0 } };
void initFile() {
if ((myfile = fopen(fileLoc, "w")) == NULL) {
printf("didnt open");
return;
}
}
void closeFile() {
fclose(myfile);
}
void printBoard() {
fprintf(myfile, ",\"");
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
fprintf(myfile, "%d", board[i][j]);
if (j == 8) {
if(i!=8)
fprintf(myfile, "//");
}
else
fprintf(myfile, ",");
}
}
fprintf(myfile, "\" ");
}

void getPossibleMoves(int *possibleMoves[], int x, int y) {
int cpX = x / 3;
cpX *= 3;
int cpY = y / 3;
cpY *= 3;
int cpB[3][3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++)
cpB[i][j] = board[cpX + i][cpY + j];
}
int psbleMoves[9] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
if (psbleMoves[i] == cpB[j][k])
psbleMoves[i] = 0;
}
}
for (int j = 0; j < 9; j++) {
if (psbleMoves[i] == board[x][j] || psbleMoves[i] == board[j][y])
psbleMoves[i] = 0;
}
}
int numMoves = 0;
for (int i = 0; i < 9; i++) {
if (psbleMoves[i] != 0)
numMoves++;
}
*possibleMoves = new int[numMoves + 1];//(int*)malloc((numMoves+1)*sizeof(int));
(*possibleMoves)[0] = numMoves;
int prevInt = 1;
for (int i = 0; i < 9; i++) {
if (psbleMoves[i] != 0) {
(*possibleMoves)[prevInt] = psbleMoves[i];
prevInt++;
}
}
}

void generateBoard() {
for (int i = 0; i < 9; i++)
board[0][i] = i+1;
for (int i = 1; i < 9; i++) {
for (int j = 0; j < 9; j++)
board[i][j] = 0;
}
int prevMove;
int *possibleMoves=new int[10];
int *prevMoves=new int[10];
for (int i = 1; i < 9; i++) {
for (int j = 0; j < 9; j++) {
prevMove = 0;
getPossibleMoves(&possibleMoves, i, j);
while (possibleMoves[0] == 0) {
prevMove++;
if (prevMoves[0] < prevMove) {
//generateBoard();
return;
}
else {
if (j != 0)
board[i][j-1] = prevMoves[prevMove + 1];
else
board[i - 1][8] = prevMoves[prevMove+1];
getPossibleMoves(&possibleMoves, i, j);
}
}
board[i][j] = possibleMoves[1];
prevMove = 0;
delete(prevMoves);
prevMoves = possibleMoves;
}
}
delete(possibleMoves);
}

int main() {
initFile();
generateBoard();
printBoard();
closeFile();
return 0;
}


By the way the output is ,"1,2,3,4,5,6,7,8,9//4,5,6,1,2,7,-33686019,-33686019,3//7,8,9,-33686019,-33686019,3,1,2,4//2,1,4,3,6,5,8,9,7//3,6,5,2,1,8,-33686019,-33686019,0//0,0,0,0,0,0,0,0,0//0,0,0,0,0,0,0,0,0//0,0,0,0,0,0,0,0,0//0,0,0,0,0,0,0,0,0"
so it doesn't finish and it doesn't have proper values at all.
Attached are what that looks like on the calculator(the really low negative values mess it up a lot), and an actual level. This is not a showcase of how the final game will look like, although I will not change it, but it just shows how the string converts to the look on the screen.
Btw here is the string for the working level that is attached: "1,0,0,0,0,0,4,8,0//5,0,0,3,0,0,0,0,2//2,0,9,0,0,4,3,5,0//8,0,6,0,5,0,0,4,3//4,2,3,0,0,0,5,7,0//0,1,5,4,0,0,9,0,0//0,0,0,0,8,0,0,0,9//6,5,0,0,9,3,0,0,4//0,8,2,6,4,0,0,0,5"
As you may be able to tell, the commas divide each element of a top down ninth of the board, and the //shes divide the top down pieces.
As you may also be able to tell, even the piece of the sudoku board that IS generated is not a legit sudoku board.
Title: Re: Sudoku Random Level Generator
Post by: JWinslow23 on October 25, 2015, 05:26:37 pm
A random Sudoku generator...this programmer (https://www.omnimaga.org/ti-z80-calculator-projects/sudoku-8x) is intrigued... (https://www.cemetech.net/forum/viewtopic.php?p=227048) :P

Myself, for my own Sudoku clone on the TI-83+/84+ (http://www.ticalc.org/archives/files/fileinfo/462/46218.html), used an on-calc random generator, except instead of generating truly random puzzles, it randomly selected from a selection of pre-made puzzles, and randomly changed it around in ways such that it was still solvable.

As I have no idea how random Sudoku puzzles are generated, I can't help you, but the method I used could artificially add at least a few more puzzles for you. I am interested to see how you tackle this, especially if you can make a random puzzle generator on the nSpire for use with your game.
Title: Re: Sudoku Random Level Generator
Post by: semiprocoder on October 25, 2015, 06:10:59 pm
Well I am kind of doing that. I think I also said previously my calc is not going to generate puzzles(maybe but not yet). lua is annoying. Anyways, I plan to generate puzzles by first filling in a board. To do this, I plan to first fill in 1,2,3,4,5..9 into the vertical column. Then I plan to get a random number that works into each of the squares. Right now I am still at that second step. First off, it is not random yet, and I cant seem to generate a working puzzle, but I think I know possibly how to do that.
Anyways, the hardest part of generating sudoku puzzles is to remove the numbers to make it an actual puzzle for each difficulty level, and to make there only 1 unique solution. I have 0 idea how to do that, and if someone were to help with that that would be awesome.
Title: Re: Sudoku Random Level Generator
Post by: JWinslow23 on October 25, 2015, 06:14:46 pm
To be honest, I have no idea how to do that either. The only way I know how to make a puzzle with only one solution is just to remove some amount of numbers from a valid filled board until the puzzle has more than one solution...but to do that, you need to check if the puzzle has only one solution...and I have no idea how to do that :P

Iirc there are algorithms online if you check. Good luck!
Title: Re: Sudoku Random Level Generator
Post by: semiprocoder on November 16, 2015, 11:40:13 pm
Ok so I finally(after not really working on it) made a generator that generates a filled board. I still have yet to remove specific tiles to make it a level though.

Here is the code(which is really simple but not very efficient, not what I originally wanted to do):

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
#include <stdlib.h>
const char* fileLoc = "easyLevels.txt";
FILE *myfile;
int *possibleMoves;
int board[9][9] = { { 0,0,0,0,0,0,0,0,0 },{ 0,0,0,0,0,0,0,0,0 },{ 0,0,0,0,0,0,0,0,0 },{ 0,0,0,0,0,0,0,0,0 },{ 0,0,0,0,0,0,0,0,0 },{ 0,0,0,0,0,0,0,0,0 },{ 0,0,0,0,0,0,0,0,0 },{ 0,0,0,0,0,0,0,0,0 },{ 0,0,0,0,0,0,0,0,0 } };
void initFile() {
if ((myfile = fopen(fileLoc, "w")) == NULL) {
printf("didnt open");
return;
}
}
void closeFile() {
fclose(myfile);
}
void printBoard() {
fprintf(myfile, ",\"");
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
fprintf(myfile, "%d", board[i][j]);
if (j == 8) {
if(i!=8)
fprintf(myfile, "//");
}
else
fprintf(myfile, ",");
}
}
fprintf(myfile, "\" ");
}

void getPossibleMoves(int *possibleMoves[], int x, int y) {
int cpX = x / 3;
cpX *= 3;
int cpY = y / 3;
cpY *= 3;
int cpB[3][3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++)
cpB[i][j] = board[cpX + i][cpY + j];
}
int psbleMoves[9] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
if (psbleMoves[i] == cpB[j][k])
psbleMoves[i] = 0;
}
}
for (int j = 0; j < 9; j++) {
if (psbleMoves[i] == board[x][j] || psbleMoves[i] == board[j][y])
psbleMoves[i] = 0;
}
}
int numMoves = 0;
for (int i = 0; i < 9; i++) {
if (psbleMoves[i] != 0)
numMoves++;
}
delete(*possibleMoves);
*possibleMoves = new int[numMoves + 1];//(int*)malloc((numMoves+1)*sizeof(int));
(*possibleMoves)[0] = numMoves;
int prevInt = 1;
for (int i = 0; i < 9; i++) {
if (psbleMoves[i] != 0) {
(*possibleMoves)[prevInt] = psbleMoves[i];
prevInt++;
}
}
}



/*void generateBoard(int i, int j, int k, int h, int f) {
if (i < 81) {
board[i % 9][i / 9] = 0;
int *possibleMoves;
getPossibleMoves(&possibleMoves, i % 9, i / 9);
if (possibleMoves[0] > 0) {
board[i % 9][i / 9] = possibleMoves[rand() % possibleMoves[0] + 1];
delete(possibleMoves);
if (j < 10) {
if (i < h) {
generateBoard(i + 1, j, k - 1, h, f);
}
else {
generateBoard(i + 1, 0, 0, i + 1, 0);
}
}
else {
if (i == h) {
if (f < 9) {
for (int l = h; l > h - k; l--)
board[l % 9][l / 9] = 0;
generateBoard(h - k, 0, k + 1, h, f + 1);
}
else {
for (int l = h; l > h - k-1; l--)
board[l % 9][l / 9] = 0;
generateBoard(h - k - 1, 0, k + 1, h, 0);
}
}
else {
generateBoard(i - 1, 0, k + 1, h, f);
}
}
}
else {
delete(possibleMoves);
generateBoard(i - 1, j+1, k+1, h, f);
}
}
else {
return;
}
return;
}*/

void generateBoard(int i, int j, int k) {
if (i < 81) {
board[i % 9][i / 9] = 0;
getPossibleMoves(&possibleMoves, i % 9, i / 9);
if (possibleMoves[0] > 0) {
board[i % 9][i / 9] = possibleMoves[rand() % possibleMoves[0] + 1];
if (i == k) {
generateBoard(i + 1, 0, i + 1);
}
else {
generateBoard(i + 1, j, k);
}
}
else {
if (i == k) {
for (int l = i; l > i - j - 1; l--)
board[l % 9][l / 9] = 0;
generateBoard(i - j - 1, j + 1, k);
}
else {
board[i % 9][i / 9] = 0;
generateBoard(i - 1, 1, i);
}
}
}
return;
}

int main() {
initFile();
generateBoard(0, 0, 0);
printBoard();
closeFile();
return 0;
}


Attached is an image of an example sudoku board made by my program in my game(as you can see I don't have a win state yet but that is really easy to make as all I have to do is check that every single square is filled).

Edit: I added a picture of what a legit sudoku level actually looks like.
Title: Re: Sudoku Random Level Generator
Post by: alexgt on November 17, 2015, 12:11:36 am
Awesome :) I have no idea how to play Sudoku and I should probably learn but it looks really promising ;)
Title: Re: Sudoku Random Level Generator
Post by: DJ Omnimaga on November 25, 2015, 08:35:50 am
Have you made any progress on this? It would definitively be cool to see how fast a genuine Sudoku level generator can run on the Nspire in Lua. Of course you could just stick to the idea of fetching from a large pool of pre-made levels, but then the file size grows much larger.
Title: Re: Sudoku Random Level Generator
Post by: semiprocoder on May 09, 2019, 05:49:57 pm
So I randomly remembered about this yesterday. When I first attempted this project, I could not figure out issues with my C sudoku generator. Armed with knowledge of C++ this time, I wrote a better(at least less convoluted) sudoku generator that appears to work correctly. In terms of speed, it is not very good - extremely easy through medium difficulty puzzles are generated rather fast, but hard takes a long time and the insane pack(added an extra difficulty cause why not?) took me about 20 minutes to generate. Right now difficulty is based purely on how many squares are not empty(extremely easy: 50-60, easy: 36-49, medium: 32-35, hard: 28-31, insane: 22-27); I took these from a source and might modify them, as the medium and hard ranges seem a little small. Here is a github link(btw was surprised to find I already made this repository) to the puzzle generator: https://github.com/awesommee333/Sudoku-Puzzle-Generation/blob/master/SudokuGenerator.cpp (https://github.com/awesommee333/Sudoku-Puzzle-Generation/blob/master/SudokuGenerator.cpp)

Therefore, since the TI NSpire is very slow, at least porting the generator I have now would not be great. I may get away with generating easy, medium, or perhaps even a single hard level(hard took a couple seconds on my computer to generate 81 levels, so *maybe* it could be used to generate 1 level in a few seconds on the TI NSpire).

Since this got me interested, I guess I will rewrite sudoku for the NSpire(gonna have to remember lua). I am not really an avid sudoku player though (I just wrote this for fun), so I will see how long this will take. For now, I guess if you want a mediocre sudoku player(which doesn't support basic features of sudoku such as different colors for starting numbers and inputted numbers), here is a link to a tns(how do you add attachments btw or is that no longer supported?): http://www.filedropper.com/sudoku_1 (http://www.filedropper.com/sudoku_1)