* WalrusIRC

You need to have 5 posts and not be part of restricted usergroups in order to use the WalrusIRC embedded shoutbox. However, you can also access our IRC channel called #CodeWalrus via EFnet.

Author Topic: Sudoku Random Level Generator  (Read 1295 times)

0 Members and 1 Guest are viewing this topic.

Offline semiprocoder

  • Full User
  • Join Date: May 2015
  • Location:
  • Posts: 277
  • Post Rating Ratio: +2/-0
    • awesommee333
    • 114/11470
    • View Profile
  • Gender: Male
Sudoku Random Level Generator
« 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:

Code: [Select]
#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.
« Last Edit: October 25, 2015, 02:15:48 am by semiprocoder »


  • Calculators owned: ti nspire, ti 84 plus se
My cemetech username is awesommee333.

Offline JWinslow23

  • Pi is wrong. Tau > Pi
  • Super User
  • CW 4x3 challenge - 2nd place
  • *
  • Join Date: May 2015
  • Location: Somewhere between 13 and Graham's Number
  • Posts: 700
  • Post Rating Ratio: +9/-1
  • Pi is wrong. Use Tau...it's easier than Pi!
    • @UCu_9qD95nADzc-W6RN-3Z8A
    • 113/11328
    • View Profile
  • Gender: Male
Re: Sudoku Random Level Generator
« Reply #1 on: October 25, 2015, 05:26:37 pm »
A random Sudoku generator...this programmer is intrigued... :P

Myself, for my own Sudoku clone on the TI-83+/84+, 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.

Offline semiprocoder

  • Full User
  • Join Date: May 2015
  • Location:
  • Posts: 277
  • Post Rating Ratio: +2/-0
    • awesommee333
    • 114/11470
    • View Profile
  • Gender: Male
Re: Sudoku Random Level Generator
« Reply #2 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.
  • Calculators owned: ti nspire, ti 84 plus se
My cemetech username is awesommee333.

Offline JWinslow23

  • Pi is wrong. Tau > Pi
  • Super User
  • CW 4x3 challenge - 2nd place
  • *
  • Join Date: May 2015
  • Location: Somewhere between 13 and Graham's Number
  • Posts: 700
  • Post Rating Ratio: +9/-1
  • Pi is wrong. Use Tau...it's easier than Pi!
    • @UCu_9qD95nADzc-W6RN-3Z8A
    • 113/11328
    • View Profile
  • Gender: Male
Re: Sudoku Random Level Generator
« Reply #3 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!

Offline semiprocoder

  • Full User
  • Join Date: May 2015
  • Location:
  • Posts: 277
  • Post Rating Ratio: +2/-0
    • awesommee333
    • 114/11470
    • View Profile
  • Gender: Male
Re: Sudoku Random Level Generator
« Reply #4 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):
Code: [Select]
#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.
« Last Edit: November 17, 2015, 02:14:34 am by semiprocoder »
  • Calculators owned: ti nspire, ti 84 plus se
My cemetech username is awesommee333.

Offline alexgt

  • Just your friendly neighborhood Ninja Stach Fancy Iron Man
  • Super User
  • Join Date: Dec 2014
  • Location: Behind you
  • Posts: 2610
  • Post Rating Ratio: +6/-1
  • Something should go here...
    • /u/alexgt9123
    • View Profile
  • Gender: Male
Re: Sudoku Random Level Generator
« Reply #5 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 ;)
  • Calculators owned: Ti-84+, Ti-Nspire, Hp Prime, Broken HP Prime, HP 48SX

Offline DJ Omnimaga

  • Omni founder & CW co-founder
  • CodeWalrus Staff
  • Super User
  • Forum Maintenance
  • Original 5
  • CodeWalrus Supporter
  • *
  • Topic Management
  • Join Date: Nov 2014
  • Location: Quebec, Canada
  • Posts: 17500
  • Post Rating Ratio: +83/-4
    • dj_omnimaga
    • DJOmnimaga.music
    • @DJOmnimaga
    • dj_omnimaga
    • @DJOmnimaga
    • /u/DJ_Omnimaga
    • DJOmnimaga
    • 112/11286
    • @djomnimaga
    • @DJOmnimaga
    • View Profile
    • DJ Omnimaga music store
  • Gender: Male
Re: Sudoku Random Level Generator
« Reply #6 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.
  • Calculators owned: TI-73, TI-80 (broken), TI-81, TI-82, TI-83, TI-83+ (broken), TI-83+ (broken), TI-83+SE (broken), TI-84+, TI-84+CSE, TI-84+CE, TI-85, TI-86, TI-89T, TI-92, TI-Nspire, TI-Nspire CX (semi-broken), HP 39gII, HP Prime, Casio fx-7000G, fx-7400G+, fx-7700GE, fx-9750G+, fx-9750GII, fx-9860G, cfx-9850G, FX-1.0+, fx-CG10, fx-CP400
  • Consoles, mobile devices and vintage computers owned: Samsung i5510, Nexus 5, Atari 2600, Lynx, SMS, Game Gear, Genesis, Dreamcast, NES, SNES, N64, GCN, Wii, Wii U, GBA, DS, 3DS, PS2, PS3, PS4, PSP, PSVita, XBox 360, XBOne

Bandcamp|Reverbnation|Facebook|Youtube|Twitter
Retired Omnimaga admin (2001-11) and editor (2012-14)
??? ??? ??? ???

 


You can also use the following HTML or bulletin board code to share it on your page or forum signature!


Also do not forget to check our affiliates below.
Planet Casio TI-Planet Calc.news BroniesQC BosaikNet Velocity Games