/*
 *  File:   sudoku.cpp
 *  Descr:  Implementation of sudoku generator and solver
 *  Author: Mats Byggmastar <mats.byggmastar@multi.fi>
 *  Date:   23.07.2005
 */

#include "sudoku.h"
#include <string.h>

#define VERSION_STR "Sudoku v1.0"

static unsigned long seed = 0;

static int get_random(int limit)
{
    seed = 1664525 * seed + 1013904223;
    return (int) ((double)limit * seed / ((double) 0xFFFFFFFF + 1.0));
}

static int get_bitcount(int choises)
{
    int count = 0;
    for (int i=1; i <= 9; i++) {
        count += (choises >> i) & 1;
    }
    return count;
}

static int get_choises(int x, int y, int numbers[9][9])
{
    int bits = 0;
    if (numbers[y][x]) {
        return 0; // no choises, number already set
    }
    for (int i=0; i < 9; i++) {
        bits |= 1 << numbers[y][i]; // horizontal
        bits |= 1 << numbers[i][x]; // vertical
        bits |= 1 << numbers[(y/3)*3 + i/3][(x/3)*3 + i%3]; // 3x3 box
    }
    return ~bits & 0x3FE;
}

static int count_numbers(int numbers[9][9])
{
    int count = 0;
    for (int y=0; y < 9; y++) {
        for (int x=0; x < 9; x++) {
            if (numbers[y][x]) {
                count++;
            }
        }
    }
    return count;
}

static bool generate(int numbers[9][9])
{
    int bitcount, choises, pos, count, i;
    int least_bitcount, save_choises, save_pos;

    memset(numbers, 0, sizeof(int[9][9]));
    for (count=0; count < 9*9; count++) { // find cell with least choises
        least_bitcount = 10; 
        pos = get_random(9*9);
        for (i=0; i < 9*9; i++) {
            choises = get_choises(pos % 9, pos / 9, numbers);
            bitcount = get_bitcount(choises);
            if (bitcount && (bitcount < least_bitcount)) {
                least_bitcount = bitcount;
                save_choises = choises;
                save_pos = pos;
            }
            pos = (pos + 1) % (9*9);
        }
        if (least_bitcount == 10) { // this game can not be solved
            return false; 
        }
        for (;;) { // randomly select one of the choises, and set it
            i = 1 + get_random(9);
            if (save_choises & (1 << i)) {
                numbers[save_pos / 9][save_pos % 9] = i;
                break;
            }
        }
    }
    return true;
}

static void hide_numbers(int numbers[9][9])
{
    int box[3][3], temp_num[9][9], work_num[9][9], pos, i, min;
    int save_pos;

    memcpy(temp_num, numbers, sizeof(int[9][9]));
    memset(numbers, 0, sizeof(int[9][9]));
    memset(box, 0, sizeof(int[3][3]));
    do
    {
        // randomly select 3x3 box with least number of numbers
        min = 10;
        pos = get_random(3*3);
        for (i=0; i < 3*3; i++) {
            if (min > box[pos / 3][pos % 3]) {
                min = box[pos / 3][pos % 3];
                save_pos = pos;
            }
            pos = (pos + 1) % (3*3);
        }
        box[save_pos / 3][save_pos % 3]++;
        // randomly add number to selected 3x3 box
        pos = get_random(3*3);
        for (i=0; i < 3*3; i++) {
            if (numbers[(save_pos/3)*3 + pos/3][(save_pos%3)*3 + pos%3] == 0) {
                numbers[(save_pos/3)*3 + pos/3][(save_pos%3)*3 + pos%3] = 
                    temp_num[(save_pos/3)*3 + pos/3][(save_pos%3)*3 + pos%3];
                break;
            }
            pos = (pos + 1) % (3*3);
        }
        memcpy(work_num, numbers, sizeof(int[9][9]));
    }
    while (!solve_sudoku(work_num));
}

bool solve_sudoku(int numbers[9][9])
{
    int bitcount, choises, pos, count, i;

    count = count_numbers(numbers);
    for (; count < 9*9; count++) { 
        for (pos=0; pos < 9*9; pos++) { // find cell with only one choise
            choises = get_choises(pos % 9, pos / 9, numbers);
            bitcount = get_bitcount(choises);
            if (bitcount == 1) {
                for (i=1; i <= 9; i++) {
                    if (choises & (1 << i)) {
                        numbers[pos / 9][pos % 9] = i;
                        break;
                    }
                }
                break;
            }
        }
        if (pos >= 9*9) { // game can not be solved
            return false; 
        }
    }
    return true;
}

bool generate_sudoku(int numbers[9][9], int game)
{
    unsigned long old_seed, save_seed;
    int visible, i, least_visible, work_num[9][9];

    seed = game;
    if (!generate(numbers)) {
        return false;
    }
    least_visible = 9*9+1;
    for (i=0; i < 200; i++) {
        memcpy(work_num, numbers, sizeof(int[9][9]));
        old_seed = seed;
        hide_numbers(work_num);
        visible = count_numbers(work_num);
        if (least_visible > visible) {
            least_visible = visible;
            save_seed = old_seed;
        }
    }
    seed = save_seed;
    hide_numbers(numbers);
    return true;
}

const char * sudoku_generator_version()
{
    return VERSION_STR;
}