# Futoshiki Task

This task implements the Futoshiki puzzle game, which is a logic puzzle where players need to fill a grid with numbers following specific rules and constraints.

## Game Rules

1. The puzzle is played on an n x n grid, filling in the numbers so that each row and column contains all the numbers from 1 to n without repetition.
2. There are inequality signs (greater than ">" or less than "<") between certain squares in the grid. These inequality signs indicate the numerical relationship between two neighboring grids.
3. Some grids will give pre-filled numbers as hints.
4. The questions are given as matrices and are accompanied by inequality constraints below in the form (row i, column j) > (row x, column y)

## Directory Structure

- `scripts/`: Contains the main implementation code
  - `futoshiki_generator.py`: Generates valid Futoshiki puzzles
  - `futoshiki_verifier.py`: Verifies solutions against game rules
  - `futoshiki_prompt.py`: Contains prompt templates in English and Chinese
- `data/`: Contains puzzle data and examples

## Implementation Components

### Generator (`futoshiki_generator.py`)
- Generates a valid N*N grid that satisfies Sudoku rules
- Randomly selects `num_inequality_signs` coordinate pairs and assigns inequality signs
- Randomly selects `num_prefilled_coords` coordinates to keep as hints
- Generates the prompt based on the above information
- Includes both English and Chinese prompt templates

### Verifier (`futoshiki_verifier.py`)
Checks if a solution is valid by verifying:
- Sudoku rules: Each row and column contains numbers 1-N exactly once
- Pre-filled numbers: The solution preserves all pre-filled numbers from the question
- Inequality constraints: All inequality signs between coordinates are satisfied

### Prompts (`futoshiki_prompt.py`)
- Contains prompt templates for both English and Chinese
- The templates include detailed explanations of game rules, constraints, expected output format, and solving tips
- Randomly selects a template to provide variety


## Command-line Interface

### Generating Puzzles
```bash
cd games/tasks/futoshiki/scripts
python futoshiki_generator.py --grid_size 4 --num_inequality_signs 4 --num_prefilled_coords 2 --num_samples 10
```

Parameters:
- `--grid_size`: Size of the grid (default: 4)
- `--num_inequality_signs`: Number of inequality signs (default: 4)
- `--num_prefilled_coords`: Number of pre-filled coordinates (default: 2)
- `--num_samples`: Number of samples to generate (default: 10)
- `--is_chinese`: Generate Chinese prompts (optional flag)
- `--output`: Specify custom output filename (optional)

### Using the Run Script
For convenience, a run script is provided to generate standard datasets:

```bash
cd reasonreason
./games/tasks/futoshiki/run.sh
```

This script will generate 4 different datasets (1000 samples each):
1. 4x4 grid with 2 inequality signs and 2 pre-filled coordinates
2. 4x4 grid with 4 inequality signs and 3 pre-filled coordinates
3. 5x5 grid with 7 inequality signs and 4 pre-filled coordinates
4. 5x5 grid with 10 inequality signs and 5 pre-filled coordinates

The files will be saved with descriptive names in the data directory.



## Example

### Question Format:
```
Current puzzle:
X X X X
X X X X
X X 2 X
X X X X

Inequality constraints:
(1,3)<(1,4)
(1,4)<(2,4)
(2,4)<(3,4)
(2,1)<(2,2)

Please provide each element in order from left to right, and from top to bottom, with each element separated by a space and each row separated by a comma. Ensure that your final answer is wrapped in double square brackets.
```

### Answer Format:
```
[[4 3 1 2,1 2 4 3,3 1 2 4,2 4 3 1]]
```

## Output Format

The generator produces data in JSONL format with the following fields:
- `question`: The formatted puzzle prompt
- `answer`: The correct solution grid (for reference)
- `metadata`: Additional information about the puzzle
  - `grid_size`: Size of the grid
  - `num_inequality_signs`: Number of inequality constraints
  - `num_prefilled_coords`: Number of pre-filled numbers
  - `prefilled_coords`: Coordinates of pre-filled numbers
  - `constraints`: List of inequality constraints

## Task Requirements

The task requires AI models to:
1. Understand complex logical constraints and rules.
2. Implement deductive reasoning to solve the puzzle.
3. Provide the solution in the required format.
4. Handle the constraints while ensuring each row and column follows the Sudoku rule.

Success is measured by:
1. Correct adherence to the Sudoku rules (each row and column contains 1-N once).
2. Preservation of pre-filled numbers in the solution.
3. Satisfaction of all inequality constraints between cells.

## Setup and Usage

### Prerequisites
- Python 3.6+
- NumPy

### Installation
No special installation required beyond the prerequisites.

### Workflow
1. Generate puzzle data (choose one of these options):
   
   a. Using run.sh (recommended):
   ```bash
   cd reasonreason
   ./games/tasks/futoshiki/run.sh
   ```
   
   b. Custom generation:
   ```bash
   cd games/tasks/futoshiki/scripts
   python futoshiki_generator.py --grid_size 4 --num_inequality_signs 4 --num_prefilled_coords 2 --num_samples 10 --output custom_puzzles.jsonl
   ```


## Available Datasets

The run.sh script generates the following data files:

| Filename | Grid Size | Inequality Signs | Pre-filled Coordinates | Samples |
|----------|-----------|------------------|------------------------|---------|
| futoshiki_4x4_ineq2_prefilled2.jsonl | 4x4 | 2 | 2 | 1000 |
| futoshiki_4x4_ineq4_prefilled3.jsonl | 4x4 | 4 | 3 | 1000 |
| futoshiki_5x5_ineq7_prefilled4.jsonl | 5x5 | 7 | 4 | 1000 |
| futoshiki_5x5_ineq10_prefilled5.jsonl | 5x5 | 10 | 5 | 1000 |

These datasets provide a diverse range of difficulty levels for evaluating model performance. 